Who Needs Crossings? Hardness of Plane Graph Rigidity

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...

Full description

Bibliographic Details
Main Authors: Abel, Zachary R, Demaine, Erik D, Demaine, Martin L, Eisenstat, Sarah Charmian, Lynch, Jayson R., Schardl, Tao Benjamin
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
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

Internet

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

Similar Items