The complexity of simultaneous geometric graph embedding

DOI10.7155/JGAA.00356MaRDI QIDQ5250132zbMATH OpenOpenAlexFDO

Authors Jean Cardinal, Vincent J. J. Kusters

Publication date 18 May 2015

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1302.7127

zbMATH Keywords

abstract topological graphspseudoline stretchability problem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Given a collection of planar graphs $G_1,dots,G_k$ 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 $phi:VoP$ such that the induced straight-line drawings of $G_1,dots,G_k$ under $phi$ are all plane. This problem is polynomial-time equivalent to weak rectilinear realizability of abstract topological graphs, which Kynv{c}l (doi:10.1007/s00454-010-9320-x) proved to be complete for $existsmathbbR$, 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 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 $k$-SGE, with the property that both numbers $k$ and $n$ are linear in the number of pseudolines. This implies not only the $existsmathbbR$-hardness result, but also a $2^{2^{Omega(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 Kynv{c}l's proof is only $2^{2^{Omega(sqrtn)}}$.

Recommendations

• Simultaneous Geometric Graph Embeddings
• Simultaneous embedding of embedded planar graphs
• Simultaneous embedding of embedded planar graphs
• Simultaneous Graph Embeddings with Fixed Edges
• On the complexity of some geometric problems with fixed parameters

Cited in

(9)

• Reconstructing point set order types from radial orderings
• Reconstructing Point Set Order Types from Radial Orderings
• The complexity of drawing a graph in a polygonal region
• Fixed points, Nash equilibria, and the existential theory of the reals
• Simultaneous Geometric Graph Embeddings
• On the complexity of some geometric problems with fixed parameters
• Geometric thickness of multigraphs is \(\exists \mathbb{R} \)-complete
• Geometric thickness of multigraphs is \(\exists \mathbb{R}\)-complete
• On the complexity of simultaneous geometric embedding for edge-disjoint graphs

This page was built for publication: The complexity of simultaneous geometric graph embedding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5250132)