Csaba
D. Tóth
Associate Professor
Department of Mathematics
California State University, Northridge
Room SN 434, 18111 Nordhoff St
Northridge, CA 913308313
Phone: (818) 6772826
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 interiordisjoint 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 polynomialtime 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_{2}. 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.

Gapplanar graphs,
 Sang Won Bae, JeanFrancois Baffier, Jinhee Chun, Peter Eades, Kord Eickmeyer, Luca Grilli, SeokHee Hong, Matias Korman, Fabrizio Montecchiani, Ignaz Rutter, and Csaba D. Tóth,
 manuscript, 2017.
 (abstract)
We introduce the family of kgapplanar 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 kgapplanar graph can be drawn crossingfree 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 beyondplanar 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