Name
Abstract | ||
|---|---|---|
We exactly settle the complexity of graph realization, graph rigidity, and graph global rigidity as applied to three types of graphs: 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 u0026 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 Kempeu0027s 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. |
Year | Venue | Field |
|---|---|---|
2016 | Symposium on Computational Geometry | Discrete mathematics,Outerplanar graph,Combinatorics,Forbidden graph characterization,Matchstick graph,Book embedding,Pathwidth,Symmetric graph,1-planar graph,Planar graph,Mathematics |
DocType | Citations | PageRank |
Conference | 2 | 0.36 |
References | Authors | |
2 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zachary Abel | 1 | 57 | 10.42 |
| Erik D. Demaine | 2 | 4624 | 388.59 |
| Martin L. Demaine | 3 | 592 | 84.37 |
| Sarah Eisenstat | 4 | 53 | 7.88 |
| Jayson Lynch | 5 | 7 | 11.97 |
| Tao B. Schardl | 6 | 183 | 13.07 |