Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00356
The Complexity of Simultaneous Geometric Graph Embedding
Vol. 19, no. 1, pp. 259272, 2015. Regular paper.
Abstract Given a collection of planar graphs G_{1},...,G_{k} on the same set V of n vertices, the simultaneous geometric embedding (with mapping) problem, or simply kSGE, is to find a set P of n points in the plane and a bijection ϕ: V → P such that the induced straightline drawings of G_{1},...,G_{k} under ϕ are all plane. This problem is polynomialtime equivalent to weak rectilinear realizability of abstract topological graphs, which Kyncl (doi:10.1007/s004540109320x) proved to be complete for ∃ℝ, the existential theory of the reals. Hence the problem kSGE is polynomialtime equivalent to several other problems in computational geometry, such as recognizing intersection graphs of line segments or finding the rectilinear crossing number of a graph. We give an elementary reduction from the pseudoline stretchability problem to kSGE, with the property that both numbers k and n are linear in the number of pseudolines. This implies not only the ∃ℝhardness result, but also a 2^{2Ω(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 simultaneously embedded, but every simultaneous drawing requires an exponential number of bits per coordinates. The best value that can be extracted from Kyncl's proof is only 2^{2Ω(√n)}.

Submitted: November 2014.
Reviewed: February 2015.
Revised: March 2015.
Accepted: April 2015.
Final: April 2015.
Published: May 2015.
Communicated by
William S. Evans

Journal Supporters
