Who Needs Crossings? Hardness of Plane Graph Rigidity
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 co...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Dagstuhl Publishing
2017
|
| Online Access: | http://hdl.handle.net/1721.1/111968 https://orcid.org/0000-0002-4295-1117 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3182-1675 https://orcid.org/0000-0003-0198-3283 |
| _version_ | 1826197324047581184 |
|---|---|
| author | Abel, Zachary R Demaine, Erik D Demaine, Martin L Eisenstat, Sarah Charmian Lynch, Jayson R. Schardl, Tao Benjamin |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Abel, Zachary R Demaine, Erik D Demaine, Martin L Eisenstat, Sarah Charmian Lynch, Jayson R. Schardl, Tao Benjamin |
| author_sort | Abel, Zachary R |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T10:46:14Z |
| format | Article |
| id | mit-1721.1/111968 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:46:14Z |
| publishDate | 2017 |
| publisher | Dagstuhl Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1119682022-09-30T22:52:58Z Who Needs Crossings? Hardness of Plane Graph Rigidity Abel, Zachary R Demaine, Erik D Demaine, Martin L Eisenstat, Sarah Charmian Lynch, Jayson R. Schardl, Tao Benjamin Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Mathematics Abel, Zachary R Demaine, Erik D Demaine, Martin L Eisenstat, Sarah Charmian Lynch, Jayson R. Schardl, Tao Benjamin 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. 2017-10-24T18:10:09Z 2017-10-24T18:10:09Z 2016-06 Article http://purl.org/eprint/type/ConferencePaper 978-3-95977-009-5 1868-8969 http://hdl.handle.net/1721.1/111968 Abel, Zachary et al. "Who Needs Crossings? Hardness of Plane Graph Rigidity." 32nd International Symposium on Computational Geometry (SoCG 2016), June 14-17 2016, Boston, Massachusetts, USA , edited by Sandor Fekete and Anna Lubiw, Dagstuhl Publishing, June 2016 © Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B. Schardl https://orcid.org/0000-0002-4295-1117 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3182-1675 https://orcid.org/0000-0003-0198-3283 en_US http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.3 32nd International Symposium on Computational Geometry (SoCG 2016) Creative Commons Attribution 4.0 International License http://creativecommons.org/licenses/by/4.0/ application/pdf Dagstuhl Publishing Dagstuhl Publishing |
| spellingShingle | Abel, Zachary R Demaine, Erik D Demaine, Martin L Eisenstat, Sarah Charmian Lynch, Jayson R. Schardl, Tao Benjamin Who Needs Crossings? Hardness of Plane Graph Rigidity |
| title | Who Needs Crossings? Hardness of Plane Graph Rigidity |
| title_full | Who Needs Crossings? Hardness of Plane Graph Rigidity |
| title_fullStr | Who Needs Crossings? Hardness of Plane Graph Rigidity |
| title_full_unstemmed | Who Needs Crossings? Hardness of Plane Graph Rigidity |
| title_short | Who Needs Crossings? Hardness of Plane Graph Rigidity |
| title_sort | who needs crossings hardness of plane graph rigidity |
| url | http://hdl.handle.net/1721.1/111968 https://orcid.org/0000-0002-4295-1117 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3182-1675 https://orcid.org/0000-0003-0198-3283 |
| work_keys_str_mv | AT abelzacharyr whoneedscrossingshardnessofplanegraphrigidity AT demaineerikd whoneedscrossingshardnessofplanegraphrigidity AT demainemartinl whoneedscrossingshardnessofplanegraphrigidity AT eisenstatsarahcharmian whoneedscrossingshardnessofplanegraphrigidity AT lynchjaysonr whoneedscrossingshardnessofplanegraphrigidity AT schardltaobenjamin whoneedscrossingshardnessofplanegraphrigidity |