Csaba D. Tóth
Associate Professor
Department of Mathematics
California State University, Northridge
Room SN 434, 18111 Nordhoff St
Northridge, CA 91330-8313
Phone: (818) 677-2826
cdtoth ♠ acm.org

---

Manuscripts

• Recognizing weak embeddings of graphs,
  • Hugo A. Akitaya, Radoslav Fulek, and Csaba D. Tóth,
  • manuscript, 2017.
  • (abstract) We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding φ:G→M of a graph G into a manifold M maps the vertices in V(G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to a common node or arc, due to data compression or low resolution. This raises the computational problem of deciding whether a given map φ:G→M comes from an embedding. A map φ:G→M is a weak embedding if it can be perturbed into an embedding ψ_ε:G→M with ∥φ-ψ_ε∥ε for every ε>0.
    A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kynčl (2017), which reduces to solving a system of linear equations over Z₂. It runs in O(n^2ω)≤O(n^4.75) time, where ω≈2.373 is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler: We perform a sequence of local operations that gradually ``untangles'' the image φ(G) into an embedding ψ(G), or reports that φ is not a weak embedding. It generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon, and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations.


• Gap-planar graphs,
  • Sang Won Bae, Jean-Francois Baffier, Jinhee Chun, Peter Eades, Kord Eickmeyer, Luca Grilli, Seok-Hee Hong, Matias Korman, Fabrizio Montecchiani, Ignaz Rutter, and Csaba D. Tóth,
  • manuscript, 2017.
  • (abstract) We introduce the family of k-gap-planar graphs, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned with at most k≥0 of its crossings. This definition finds motivation in edge casing, as a k-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We obtain results on the maximum density, drawability of complete graphs, complexity of the recognition problem, and relationships with other families of beyond-planar graphs.


• Optimal cutting of a polygon by lasers,
  • Esther Arkin, Peter Brass, Rathish Das, Jie Gao, Mayank Goswami, Joseph S.B. Mitchell, Valentin Polishchuk, and Csaba D. Tóth,
  • in Abstracts of the 26th Fall Workshop on Computational Geometry (New York, NY, 2016).

---

Publications