Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
GraphMaps: Browsing Large Graphs as Interactive Maps Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Realization of Simply Connected Polygonal Linkages and Recognition of Unit Disk Contact Trees

Authors : Clinton Bowen, Stephane Durocher, Maarten Löffler, Anika Rounds, André Schulz, Csaba D. Tóth

Published in: Graph Drawing and Network Visualization

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We wish to decide whether a simply connected flexible polygonal structure can be realized in Euclidean space. Two models are considered: polygonal linkages (body-and-joint framework) and contact graphs of unit disks in the plane. (1) We show that it is strongly NP-hard to decide whether a given polygonal linkage is realizable in the plane when the bodies are convex polygons and their contact graph is a tree; the problem is weakly NP-hard already for a chain of rectangles, but efficiently decidable for a chain of triangles hinged at distinct vertices. (2) We also show that it is strongly NP-hard to decide whether a given tree is the contact graph of interior-disjoint unit disks in the plane.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Recognizing Weighted Disk Contact Graphs
next chapter Towards Characterizing Graphs with a Sliceable Rectangular Dual
Literature
1.
Alt, H., Knauer, C., Rote, G., Whitesides, S.: On the complexity of the linkage reconfiguration problem. In: Pach, J. (ed.) Towards a Theory of Geometric Graphs, vol. 342, Contemporary Mathematics, pp. 1–14. AMS, Providence (2004)
2.
Ballinger, B., Charlton, D., Demaine, E.D., Demaine, M.L., Iacono, J., Liu, C.-H., Poon, S.-H.: Minimal locked trees. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 61–73. Springer, Heidelberg (2009) CrossRef
3.
4.
Bhatt, S.N., Cosmadakis, S.S.: The complexity of minimizing wire lengths in VLSI layouts. Inform. Process. Lett. 25(4), 263–267 (1987)MATHCrossRef
5.
Breu, H., Kirkpatrick, D.G.: On the complexity of recognizing intersection and touching graphs of discs. In: Brandenburd, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 88–98. Spinger, Heidelberg (1996)
6.
7.
Cabello, S., Demaine, E.D., Rote, G.: Planar embeddings of graphs with specified edge lengths. J. Graph Alg. Appl. 11(1), 259–276 (2007)MATHMathSciNetCrossRef
8.
Cheong, J.-S., van der Stappen, A.F., Goldberg, K., Overmars, M.H., Rimon, E.: Immobilizing hinged polygons. Int. J. Comput. Geom. Appl. 17(1), 45–70 (2007)MATHCrossRef
9.
Connelly, R., Demaine, E.D.: Geometry and topology of polygonal linkages. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, ch. 9, pp. 197–218. CRC, Boca Raton (2004)
10.
Connelly, R., Demaine, E.D., Rote, G.: Straightening polygonal arcs and convexifying polygonal cycles. Discrete Comput. Geom. 30(2), 205–239 (2003)MATHMathSciNetCrossRef
11.
Connelly, R., Demaine, E.D., Demaine, M.L., Fekete, S.P., Langerman, S., Mitchell, J.S.B., Ribó, A., Rote, G.: Locked and unlocked chains of planar shapes. Discrete Comput. Geom. 44(2), 439–462 (2010)MATHMathSciNetCrossRef
12.
Demaine, E.D., Eppstein, D., Erickson, J., Hart, G.W., O’Rourke, J.: Vertex-unfoldings of simplicial manifolds. In: 18th Sympos. on Comput. Geom., pp. 237–243. ACM Press, New York (2002)
13.
14.
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, Upper Saddle River (1999)MATH
15.
Eades, P., Whitesides, S.: The realization problem for Euclidean minimum spanning trees is NP-hard. Algorithmica 16(1), 60–82 (1996)MATHMathSciNetCrossRef
16.
17.
Fekete, S.P., Houle, M.E., Whitesides, S.: The wobbly logic engine: Proving hardness of non-rigid geometric graph representation problems. In: Di Battista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 272–283. Springer, Heidelberg (1997)
18.
19.
Hliněný, P.: Touching graphs of unit balls. In: Di Battista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 350–358. Springer, Heidelberg (1997)
20.
Hliněný, P., Kratochvíl, J.: Representing graphs by disks and balls (a survey of recognition-complexity results). Discrete Math. 229(1–3), 101–124 (2001)MATHMathSciNetCrossRef
21.
Klemz, B., Nöllenburg, M., Prutkin, R.: Recognizing weighted disk contact graphs. In: Di Giacomo, E., Lubiw, A. (eds.) GD 2015. LNCS, vol. 9411, pp. 433–446. LNCS, Spinger, Heidelberg (2015)
22.
Reif, J.H.: Complexity of the mover’s problem and generalizations. In: 20th FoCS, pp. 421–427. IEEE, New York (1979)
23.
Schaefer, M.: Realizability of graphs and linkages. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 461–482. Springer, Heidelberg (2013)CrossRef
24.
25.
Metadata
Title
Realization of Simply Connected Polygonal Linkages and Recognition of Unit Disk Contact Trees
Authors
Clinton Bowen
Stephane Durocher
Maarten Löffler
Anika Rounds
André Schulz
Csaba D. Tóth
Copyright Year
2015
Book
Graph Drawing and Network Visualization

Print ISBN: 978-3-319-27260-3

Electronic ISBN: 978-3-319-27261-0

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-27261-0_37

Premium Partner

    Image Credits