Go to the corresponding LIPIcs Volume Portal |
Abel, Zachary ;
Demaine, Erik D. ;
Demaine, Martin L. ;
Eisenstat, Sarah ;
Lynch, Jayson ;
Schardl, Tao B.
Who Needs Crossings? Hardness of Plane Graph Rigidity
pdf-format:
LIPIcs-SoCG-2016-3.pdf (0.7 MB)
Abstract
We exactly settle the complexity of graph realization, graph rigidity, and graph global rigidity as applied to three types of graphs: "globally noncrossing" graphs, which avoid crossings in all of their configurations; matchstick graphs, with unit-length edges and where only noncrossing configurations are considered; and unrestricted graphs (crossings allowed) with unit edge lengths (or in the global rigidity case, edge lengths in {1,2}). We show that all nine of these questions are complete for the class Exists-R, defined by the Existential Theory of the Reals, or its complement Forall-R; in particular, each problem is (co)NP-hard.
One of these nine results - that realization of unit-distance graphs is Exists-R-complete - was shown previously by Schaefer (2013), but the other eight are new. We strengthen several prior results. Matchstick graph realization was known to be NP-hard (Eades & Wormald 1990, or Cabello et al. 2007), but its membership in NP remained open; we show it is complete for the (possibly) larger class Exists-R. Global rigidity of graphs with edge lengths in {1,2} was known to be coNP-hard (Saxe 1979); we show it is Forall-R-complete.
The majority of the paper is devoted to proving an analog of Kempe's Universality Theorem - informally, "there is a linkage to sign your name" - for globally noncrossing linkages. In particular, we show that any polynomial curve phi(x,y)=0 can be traced by a noncrossing linkage, settling an open problem from 2004. More generally, we show that the nontrivial regions in the plane that may be traced by a noncrossing linkage are precisely the compact semialgebraic regions. Thus, no drawing power is lost by restricting to noncrossing linkages. We prove analogous results for matchstick linkages and unit-distance linkages as well.
BibTeX - Entry
@InProceedings{abel_et_al:LIPIcs:2016:5895,
author = {Zachary Abel and Erik D. Demaine and Martin L. Demaine and Sarah Eisenstat and Jayson Lynch and Tao B. Schardl},
title = {{Who Needs Crossingsl Hardness of Plane Graph Rigidity}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {3:1--3:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5895},
URN = {urn:nbn:de:0030-drops-58951},
doi = {10.4230/LIPIcs.SoCG.2016.3},
annote = {Keywords: Graph Drawing, Graph Rigidity Theory, Graph Global Rigidity, Linkages, Complexity Theory, Computational Geometry}
}
Keywords:
Graph Drawing, Graph Rigidity Theory, Graph Global Rigidity, Linkages, Complexity Theory, Computational Geometry
Collection:
32nd International Symposium on Computational Geometry (SoCG 2016)
Issue Date:
2016
Date of publication:
10.06.2016