The complexity of simultaneous geometric graph embedding
Jean Cardinal, Vincent J. J. Kusters · 2015
Given a collection of planar graphs G1,..., Gk on the same set V of n vertices, the simultaneous geometric embedding (with mapping) problem, or simply k-SGE, is to find a set P of n points in the plane and a bijection ϕ: V → P such that the induced straight-line drawings of G1,..., Gk under ϕ are all plane. This problem is polynomial-time equivalent to weak rectilinear realiz-ability of abstract topological graphs, which Kynčl (doi:10.1007/s00454-010-9320-x) proved to be complete for ∃R, the existential theory of the reals. Hence the problem k-SGE is polynomial-time equivalent to several other problems in computational geometry, such as recognizing intersec-tion graphs of line segments or finding the rectilinear crossing number of a graph. We give an elementary reduction from the pseudoline stretchability problem to k-SGE, with the property that both numbers k and n are lin-ear in the number of pseudolines. This implies not only the ∃R-hardness result, but also a 22 Ω(n) lower bound on the minimum size of a grid on which any such simultaneous embedding can be drawn. This bound is tight. Hence there exists such collections of graphs that can be simultane-ously embedded, but every simultaneous drawing requires an exponential number of bits per coordinates. The best value that can be extracted from Kynčl’s proof is only 22 Ω(