 Realizability of Graphs and LinkagesMarcus Schaefer ()
A chapter in Thirty Essays on Geometric Graph Theory, 2013, pp 461-482 from Springer Abstract: Abstract We show that deciding whether a graph with given edge lengths can be realized by a straight-line drawing has the same complexity as deciding the truth of sentences in the existential theory of the real numbers, ETR; we introduce the class $$\exists \mathbb{R}$$ that captures the computational complexity of ETR and many other problems. The graph realizability problem remains $$\exists \mathbb{R}$$ -complete if all edges have unit length, which implies that recognizing unit distance graphs is $$\exists \mathbb{R}$$ -complete. We also consider the problem for linkages: In a realization of a linkage, vertices are allowed to overlap and lie on the interior of edges. Linkage realizability is $$\exists \mathbb{R}$$ -complete and remains so if all edges have unit length. A linkage is called rigid if any slight perturbation of its vertices that does not break the linkage (i.e., keeps edge lengths the same) is the result of a rigid motion of the plane. Testing whether a configuration is not rigid is $$\exists \mathbb{R}$$ -complete. Keywords: Existential Theory; Graph Drawing; Graph Realizability; Euclidean Dimension; Nontrivial Zero (search for similar items in EconPapers) There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it. Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-0110-0_24 Ordering information: This item can be ordered from DOI: 10.1007/978-1-4614-0110-0_24 Access Statistics for this chapter More chapters in Springer Books from Springer |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.