Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

Realizability of Graphs and Linkages

verfasst von : Marcus Schaefer

Erschienen in: Thirty Essays on Geometric Graph Theory

Verlag: Springer New York

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Coloring Distance Graphs and Graphs of Diameters
Nächstes Kapitel Equilateral Sets in
Fußnoten
1
A manuscript collecting many of these problems is in preparation (Schaefer, The real logic of drawing graphs, personal communication).
 
2
When writing formulas in the existential theory of the reals, we will freely use integers and rationals, since these can easily be eliminated without affecting the length of the formula substantially. We will also drop the symbol ∗ .
 
3
Tarski showed that the full theory of the reals is decidable by quantifier elimination.
 
4
This reducibility is known as polynomial-time many–one reducibility; since we have no need for other reducibilities in this chapter, we simplify to “reduces.” We consider decision problems (requiring a “yes” or “no” answer) encoded as sets of binary strings; that is, \(A,B \subseteq \{ 0, {1\}}^{{_\ast}}\), and \(f :\{ 0, {1\}}^{{_\ast}}\rightarrow \{ 0, {1\}}^{{_\ast}}\). For more background on encodings and basic definitions from computational complexity including complexity classes NP (nondeterministic polynomial time) and PSPACE (polynomial space), see any of the standard references, e.g., [35, 44]. We could have replaced polynomial time with logarithmic space in the definition of ≤ m but decided to use the more familiar notion.
 
5
So “A reduces to B” does not mean that B is easier than A, as the word “reduces” may incorrectly suggest.
 
6
The statement in [2] contains a typo in the radius of the ball.
 
7
For a discussion of graph drawing assumptions, see [47].
 
8
Our distinction between the realizability of graphs and linkages is not universal, but not unusual; for linkages, [10] is a good reference; for graph realizability, definitions and terminology vary. For instance, realizable graphs are sometimes called Euclidean graphs. Often the definitions allow that vertices lie on edges of which they are not endpoints, though that may in some cases be due to oversight; as we will see, from a computational point of view, this distinction does not matter.
 
9
There are many applets implementing Peaucellier’s linkage available on the web to play with [30]. James Joseph Sylvester writes about Lord Kelvin that he “nursed it as if it had been his own child, and when a motion was made to relieve him of it, replied ‘No! I have not had nearly enough of it—it is the most beautiful thing I have ever seen in my life’.” [46]. There have been other devices, both earlier and later, achieving the same effect, see [26] for an early history.
 
10
Erdős et al.  [16] defined the dimension of a graph using (noninduced) subgraphs of E n . Later, Erdős and Simonovits [15] introduced Euclidean dimension under the name faithful dimension. The two notions differ: Take a wheel W 6 with six spokes and remove one of the spokes. The resulting graph is realizable as a subgraph, but not as an induced subgraph of E 2. The name “Euclidean dimension” seems to be due to Maehara [31]. For details and more terminology and history, see [45, Sect. 13.2].
 
11
See [25] or [11, Sect. 3.2.1] for detailed expositions.
 
12
Kempe used a parallelism gadget like this in his proof of the universality theorem that every bounded part of an algebraic curve can be traced by a suitable linkage. His parallelism gadget was flawed, however; there are many ways to repair the construction. We follow a construction due to Kapovich and Millson [25], also described in [11, Sect. 3.2.2].
 
13
The realization of the Moser graph is not unique; both of the diamonds can flip; to force d and e to be realized at distance < 1 ∕ 2 as shown in Fig. 4, we brace the construction by adding edges gx, xy, and yb of lengths w(gx) = 1, w(xy) = 3, w(yb) = 1; this forces g and b to have distance at least 1, thereby forcing the intended realization of the Moser graph.
 
14
The name H 2 N seems to be short for Hilbert’s homogeneous Nullstellensatz [27].
 
15
This is a folklore result; for example, it is easy to see that STRETCHABILITY can be rephrased like this. The version in the Blum–Shub–Smale model can be found in [6].
 
16
The reduction is polynomial time, since our polynomials have total degree 2.
 
Literatur
1.
T.G. Abbott, Generalizations of Kempe’s universality theorem. Master’s thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, Cambridge, MA, 2008
2.
S. Basu, R. Pollack, M.-F. Roy, Algorithms in real algebraic geometry, in Algorithms and Computation in Mathematics, vol. 10, 2nd edn. (Springer, Berlin, 2006)
3.
4.
A. Björner, M.L. Vergnas, B. Sturmfels, N. White, G.M. Ziegler, Oriented matroids, in Encyclopedia of Mathematics and Its Applications, vol. 46, 2nd edn. (Cambridge University Press, Cambridge, 1999)
5.
J. Blömer, A probabilistic zero-test for expressions involving roots of rational numbers, in Algorithms—ESA ’98 (Venice). Lecture Notes in Computer Science, vol. 1461 (Springer-Verlag, Berlin, 1998), pp. 151–162
6.
L. Blum, M. Shub, S. Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Am. Math. Soc. (N.S.) 21(1), 1–46 (1989)
7.
S. Cabello, E.D. Demaine, G. Rote, Planar embeddings of graphs with specified edge lengths. J. Graph Algorithm. Appl. 11(1), 259–276 (electronic) (2007)
8.
J. Canny, Some algebraic and geometric computations in pspace, in STOC ’88: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (ACM, New York, 1988), pp. 460–469
9.
V. Chvátal, D.A. Klarner, D.E. Knuth, Selected combinatorial research problems. Technical Report STAN-CS-72-292, Computer Science Department, Stanford University, Palo Alto, CA, 1972
10.
R. Connelly, E.D. Demaine, Geometry and topology of polygonal linkages, in Handbook of Discrete and Computational Geometry, ed. by J.E. Goodman, J. O’Rourke (CRC Press, West Palm Beach, FL, 2004)
11.
E.D. Demaine, J. O’Rourke, Geometric Folding Algorithms (Cambridge University Press, Cambridge, 2007); Linkages, origami, polyhedra
12.
13.
14.
15.
P. Erdős, M. Simonovits, On the chromatic number of geometric graphs. Ars Combin. 9, 229–246 (1980)MathSciNet
16.
17.
18.
J.E. Goodman, J. O’Rourke (eds.), Handbook of Discrete and Computational Geometry, 2nd edn. Discrete Mathematics and Its Applications (Chapman & Hall/CRC, Boca Raton, FL, 2004)
19.
J.E. Goodman, R. Pollack, B. Sturmfels, Coordinate representation of order types requires exponential storage, in STOC ’89: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing (ACM, New York, 1989), pp. 405–410
20.
D.Yu. Grigor’ev, N.N. Vorobjov, Solving systems of polynomial inequalities in subexponential time. J. Symb. Comput. 5(1–2), 37–64 (1988)
21.
S.L. Greitzer, H.S.M. Coxeter, Geometry Revisited (The Mathematical Association of America, Washington, DC, 1967)MATH
22.
H. Hong. Comparison of several decision algorithms for the existential theory of the reals. Technical Report 91–41, RISC-Linz, Johannes Kepler University, Linz, 1991
23.
24.
25.
M. Kapovich, J.J. Millson, Universality theorems for configuration spaces of planar linkages. Topology 41(6), 1051–1107 (2002)MathSciNetMATHCrossRef
26.
A.B. Kempe, How to draw a straight line. Classics in Mathematics Education (MacMillan, London, 1977)
27.
P. Koiran, The complexity of local dimensions for constructible sets. J. Complexity 16(1), 311–323 (2000); Real computation and complexity (Schloss Dagstuhl, 1998)
28.
M. Laurent, A tour d’horizon on positive semidefinite and Euclidean distance matrix completion problems. Topics in semidefinite and interior-point methods (Toronto, ON, 1996), in Fields Institute of Communication, vol. 18 (Amer. Math. Soc., Providence, RI, 1998), pp. 51–76
29.
P. Lemke, S.S. Skiena, W.D. Smith, Reconstructing sets from interpoint distances. Discrete and computational geometry, in Algorithms Combination, vol. 25 (Springer, Berlin, 2003), pp. 507–631
30.
31.
32.
33.
B. Mishra, Computational real algebraic geometry, in Handbook of Discrete and Computational Geometry, CRC Press Ser. Discrete Math. Appl. (CRC Press, Boca Raton, FL, 1997), pp. 537–556
34.
N. E. Mnëv, The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. Topology and Geometry—Rohlin Seminar, in Lecture Notes in Mathematics, vol. 1346 (Springer-Verlag, Berlin, 1988), pp. 527–543
35.
C.H. Papadimitriou, Computational Complexity (Addison-Wesley, Reading, MA, 1994)MATH
36.
J. Renegar, On the computational complexity and geometry of the first-order theory of the reals. I. Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals. J. Symbolic Comput. 13(3), 255–299 (1992)MathSciNetMATH
37.
J. Renegar, On the computational complexity and geometry of the first-order theory of the reals. II. The general decision problem. Preliminaries for quantifier elimination. J. Symbolic Comput. 13(3), 301–327 (1992)MathSciNetMATH
38.
J. Renegar, On the computational complexity and geometry of the first-order theory of the reals. III. Quantifier elimination. J. Symbolic Comput. 13(3), 329–352 (1992)MathSciNetMATHCrossRef
39.
J. Richter-Gebert, Mnëv’s universality theorem revisited. Sém. Lothar. Combin. 34 (1995)
40.
J.B. Saxe, Embeddability of weighted graphs in k-space is strongly NP-hard, in Seventeenth Annual Allerton Conference on Communication, Control, and Computing, Proceedings of the Conference held in Monticello, Ill., Urbana, 1979. University of Illinois Department of Electrical Engineering. Proceedings of the International School of Physics “Enrico Fermi”, LXX*, pp. xiv+1036, 10–12 October 1979
41.
M. Schaefer, Complexity of some geometric and topological problems, in Graph Drawing, ed. by D. Eppstein, E.R. Gansner. Lecture Notes in Computer Science, vol. 5849 (Springer, Berlin, 2009), pp. 334–344
42.
M. Schaefer, D. Štefankovič, Fixed points, Nash equilibria, and the existential theory of the reals. Unpublished manuscript.
43.
P.W. Shor, Stretchability of pseudolines is NP-hard. Applied geometry and discrete mathematics, in DIMACS Series in Discrete Mathematical and Theoretical Computer Science, vol. 4 (Amer. Math. Soc., Providence, RI, 1991), pp. 531–554
44.
M. Sipser, Introduction to the Theory of Computation, 2nd edn. (Course Technology, Boston, 2005)
45.
A. Soifer, The Mathematical Coloring Book (Springer, New York, 2009); Mathematics of coloring and the colorful life of its creators, With forewords by Branko Grünbaum, Peter D. Johnson, Jr. and Cecil Rousseau
46.
J.J. Sylvester, On recent discoveries in mechanical conversion of motion, in Proceedings of the Royal Institution of Great Britain, London, 1875, pp. 179–198; Talk delivered 23 January 1874
47.
L.A. Székely, A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Math. 276(1–3), 331–352 (2004)MathSciNetMATHCrossRef
48.
S. Whitesides, Algorithmic issues in the geometry of planar linkage movement. Australian Comput. J. 24(2), 42–50 (1992)
49.
Y. Yemini, Some theoretical aspects of position-location problems, in 20th Annual Symposium on Foundations of Computer Science (San Juan, Puerto Rico, 1979) (IEEE, New York, 1979), pp. 1–8
Metadaten
Titel
Realizability of Graphs and Linkages
verfasst von
Marcus Schaefer
Copyright-Jahr
2013
Verlag
Springer New York
Buch
Thirty Essays on Geometric Graph Theory

Print ISBN: 978-1-4614-0109-4

Electronic ISBN: 978-1-4614-0110-0

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-1-4614-0110-0_24