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

Plane Geometric Graph Augmentation: A Generic Perspective

verfasst von : Ferran Hurtado, Csaba D. Tóth

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

Graph augmentation problems are motivated by network design and have been studied extensively in optimization. We consider augmentation problems over plane geometric graphs, that is, graphs given with a crossing-free straight-line embedding in the plane. The geometric constraints on the possible new edges render some of the simplest augmentation problems intractable, and in many cases only extremal results are known. We survey recent results, highlight common trends, and gather numerous conjectures and open problems.

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 Counting Plane Graphs: Flippability and Its Applications
Nächstes Kapitel Discrete Geometry on Red and Blue Points in the Plane Lattice
Fußnoten
1
The crossing lemma was independently proved by Leighton [73] as well.
 
Literatur
1.
M. Abellanas, A. García, F. Hurtado, J. Tejel, J. Urrutia, Augmenting the connectivity of geometric graphs. Comput. Geom. Theor. Appl. 40(3), 220–230 (2008)MATHCrossRef
2.
O. Aichholzer, S. Bereg, A. Dumitrescu, A. García, C. Huemer, F. Hurtado, M. Kano, A. Márquez, D. Rappaport, S. Smorodinsky, D. Souvaine, J. Urrutia, D. Wood, Compatible geometric matchings. Comput. Geom. Theor. Appl. 42, 617–626 (2009)MATHCrossRef
3.
O. Aichholzer, D. Bremner, E.D. Demaine, F. Hurtado, E. Kranakis, H. Krasser, S. Ramaswami, S. Sethia, J. Urrutia, Games on triangulations. Theor. Comp. Sci. 343(1–2), 42–71 (2005)MathSciNetMATHCrossRef
4.
O. Aichholzer, T. Hackl, M. Hoffmann, C. Huemer, A. Pór, F. Santos, B. Speckmann, B. Vogtenhuber, Maximizing maximal angles for plane straight line graphs, in Proceedings of the 10th Workshop on Algorithms and Data Structures, LNCS, vol. 4619 (Springer, Berlin, 2007), pp. 458–469
5.
O. Aichholzer, T. Hackl, C. Huemer, F. Hurtado, H. Krasser, B. Vogtenhuber, On the number of plane geometric graphs. Graphs Combinator. 23(1), 67–84 (2007)MathSciNetMATHCrossRef
6.
M. Ajtai, V. Chvátal, M.M. Newborn, E. Szemerédi, Crossing-free subgraphs. Ann. Discrete Math. 12, 9–12 (1982)MATH
7.
M. Al-Jubeh, M. Hoffmann, M. Ishaque, D.L. Souvaine, C.D. Tóth, Convex partitions with 2-edge connected dual graphs. J. Combin. Opt., 22(3), 409–425 (2011)MATHCrossRef
8.
M. Al-Jubeh, M. Ishaque, K. Rédei, D.L. Souvaine, C.D. Tóth, Tri-edge-connectivity augmentation for planar straight line graphs. Algorithmica 61(4), 971–999 (2011)MathSciNetMATHCrossRef
9.
N. Alon, S. Rajagopalan, S. Suri, Long non-crossing configurations in the plane. Fundam. Inform. 22(4), 385–394 (1995)MathSciNetMATH
10.
B. Aronov, K. Buchin, M. Buchin, M. Van Kreveld, M. Löffler, J. Luo, R.I. Silveira, B. Speckmann, Connect the dot: computing feed-links with minimum dilation, in Proceedings of the Algorithms Data Structures Symposium (WADS), LNCS, vol. 5664 (Springer, Berlin, 2009), pp. 49–60
11.
T. Asano, S.K. Ghosh, T.C. Shermer, in Visibility in the Plane, ed. by J.R. Sack, J. Urrutia. Handbook on Computational Geometry (Elsevier, Amsterdam, 2000), pp. 829–876
12.
F. Aurenhammer, Y. Xu, in Optimal Triangulations, ed. by C.A. Floudas, P.M. Pardalos. Encyclopedia of Optimization, vol. 4 (Kluwer, Dordrecht, 2001), pp. 160–166
13.
A. Bagheri, M. Razzazi, Planar straight-line point-set embedding of trees with partial embeddings. Inf. Proc. Lett. 110, 521–523 (2010)MathSciNetMATHCrossRef
14.
15.
P. Bose, On embedding an outer-planar graph in a point set. Comput. Geom. Theor. Appl. 23, 303–312 (2002)MATHCrossRef
16.
P. Bose, J. Gudmundsson, M. Smid, Constructing plane spanners of bounded degree and low weight. Algorithmica 42, 249–264 (2005)MathSciNetMATHCrossRef
17.
P. Bose, L. Devroye, M. Löffler, J. Snoeyink, V. Verma, The spanning ratio of the Delaunay triangulation is greater than π ∕ 2. Comput. Geom. Theor. Appl. 44(2), 121–127 (2011)MATHCrossRef
18.
P. Bose, M.E. Houle, G.T. Toussaint, Every set of disjoint line segments admits a binary tree. Discrete Comput. Geom. 26(3), 387–410 (2001)MathSciNetMATHCrossRef
19.
P. Bose, M. McAllister, J. Snoeyink, Optimal algorithms to embed trees in a point set. J. Graph Algorithm. Appl. 1(2), 1–15 (1997)MathSciNetCrossRef
20.
21.
P. Brass, E. Cenek, C. Duncan, A. Efrat, C. Erten, D. Ismailescu, S. Kobourov, A. Lubiw, J. Mitchell. On simultaneous planar graph embeddings. Comput. Geom. Theor. Appl. 36(2), 117–130 (2007)MathSciNetMATHCrossRef
22.
P. Brass, W. Moser, J. Pach, Research Problems in Discrete Geometry. (Springer, Berlin, 2005)
23.
S. Cabello, Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. J. Graph Algorith. Appl. 10, 353–363 (2006)MathSciNetMATHCrossRef
24.
I. Caragiannis, C. Kaklamanis, E. Kranakis, D. Krizanc, A. Wiese, Communication in wireless networks with directional antennas, in Proceedings of the 20th ACM Symposium on Parallel Algorithms and Architectures (ACM, New York, 2008), pp. 344–351
25.
26.
27.
M. Chrobak, H. Karloff, A lower bound on the size of universal sets for planar graphs. SIGACT News 20, 83–86 (1989)CrossRef
28.
M. Damian, R. Flatland, Spanning properties of graphs induced by directional antennas, in Proceedings 20th Fall Workshop on Computational Geometry (Stony Brook, NY, 2010)
29.
30.
T.K. Dey, M.B. Dillencourt, S.K. Ghosh, J.M. Cahill, Triangulating with high connectivity. Comput. Geom. Theor. Appl. 8, 39–56 (1997)MathSciNetMATHCrossRef
31.
G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs (Prentice Hall, Englewood Cliffs, NJ, 1998)
32.
S. Dobrev, E. Kranakis, D. Krizanc, O. Morales, J. Opatrny, L. Stacho, Strong connectivity in sensor networks with given number of directional antennae of bounded angle, in Proceedings of the 4th Conference on Combinatorial Optimization and Applications, LNCS, vol. 6509 (Springer, Berlin, 2010), pp. 72–86
33.
V. Dujmović, D. Eppstein, M. Suderman, D.R. Wood, Drawings of planar graphs with few slopes and segments. Comput. Geom. Theor. Appl. 38, 194–212 (2007)MATHCrossRef
34.
A. Dumitrescu, J. Pach, G. Tóth, Drawing Hamiltonian cycles with no large angles, in Proceedings of the 17th Symposium on Graph Drawing (GD’09), LNCS, vol. 5849 (Springer, Berlin, 2010), pp. 3–14
35.
A. Dumitrescu, A. Schulz, A. Sheffer, C.D. Tóth, Bounds on the maximum multiplicity of some common geometric graphs, in Proceedings of the Symposium on Theorerical Aspects of Computer Science (STACS), LIPICS, Schloss Dagstuhl, vol. 5 of LIPICS (Schloss Dagstuhl, Germany, 2011), pp. 637–648
36.
37.
38.
M. Farshi, P. Giannopoulos, J. Gudmundsson, Improving the stretch factor of a geometric network by edge augmentation. SIAM J. Comput. 38(1), 226–240 (2008)MathSciNetMATHCrossRef
39.
40.
S. Fialko, T.P. Mutzel, A new approximation algorithm for the planar augmentation problem, in Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, ACM Press. 1998, pp. 260–269
41.
A. Frank, Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discrete Math. 5(1), 22–53 (1992)CrossRef
42.
F. Frati, M. Kaufmann, S. Kobourov, Constrained simultaneous and near-simultaneous embeddings, in Proceedings 15th Symposium on Graph Drawing (GD’07), LNCS, vol. 4875 (Springer, Berlin, 2008), pp. 268–279
43.
44.
A. García, C. Huemer, F. Hurtado, J. Tejel, P. Valtr, On triconnected and cubic plane graphs on given point sets. Comput. Geom. Theor. Appl. 42(9), 913–922 (2009)MATHCrossRef
45.
A. García, M. Noy, J. Tejel, Lower bounds on the number of crossing-free subgraphs of K N . Comput. Geom. Theor. Appl. 16, 211–221 (2000)MATHCrossRef
46.
J. García-Lopez, M. Nicolás, Planar point sets with large minimum convex partitions, in Abstracts of the 22nd European Workshop on Computational Geometry (Delphi, Greece, 2006), pp. 51–54
47.
S.K. Ghosh, Visibility Algorithms in the Plane (Cambridge University Press, Cambridge, 2007)MATHCrossRef
48.
P. Giannopoulos, R. Klein, C. Knauer, et al., Computing geometric minimum-dilation graphs is NP-hard. Int. J. Comput. Geom. Appl. 20(2), 147–173 (2010)MathSciNetMATHCrossRef
49.
J.E. Goodman, J. O’Rourke (eds.), Handbook of Discrete and Computational Geometry, 2nd edn. (Chapman & Hall and CRC Press, Boca Raton, FL, 2004)MATH
50.
51.
C. Gutwenger, P. Mutzel, B. Zey, On the hardness and approximability of planar biconnectivity augmentation, in Proceedings of the 15th Computing and Combinatorics Conference (COCOON), LNCS, vol. 5609 (Springer, Berlin, 2009), pp. 249–257
52.
P. Gritzmann, B. Mohar, J. Pach, R. Pollack, Embedding a planar triangulation with vertices at specified points. Am. Math. Monthly 98(2), 165–166 (1991)MathSciNetCrossRef
53.
M. Hoffmann, B. Speckmann, C.D. Tóth, Pointed binary encompassing trees: simple and optimal. Comput. Geom. Theor. Appl. 43(1), 35–41 (2010)MATHCrossRef
54.
M. Hoffmann, C.D. Tóth, Alternating paths through disjoint line segments. Inf. Proc. Lett. 87(6), 287–294 (2003)MATHCrossRef
55.
M. Hoffmann, C.D. Tóth, Pointed and colored binary encompassing trees, in Proceedings of the 21st Symposium on Computational Geometry (ACM, New York, 2005), pp. 81–90
56.
M. Hoffmann, C.D. Tóth, Segment endpoint visibility graphs are Hamiltonian. Comput. Geom. Theor. Appl. 26(1), 47–68 (2003)MATHCrossRef
57.
58.
59.
F. Hurtado, M. Noy, Counting triangulations of almost-convex polygons. Ars Combinatoria 45, 169–179 (1997)MathSciNetMATH
60.
T.-S. Hsu, Simpler and faster biconnectivity augmentation. J. Algorithm. 45(1), 55–71 (2002)MATHCrossRef
61.
62.
F. Hurtado, M. Kano, D. Rappaport, C.D. Tóth, Encompassing colored crossing-free geometric graphs. Comput. Geom. Theor. Appl. 39(1), 14–23 (2008)MATHCrossRef
63.
Y. Ikebe, M.A. Perles, A. Tamura, S. Tokunaga, The rooted tree embedding problem into points in the plane. Discrete Comput. Geom. 11, 51–63 (1994)MathSciNetMATHCrossRef
64.
M. Ishaque, D.L. Souvaine, C.D. Tóth, Disjoint compatible geometric matchings, in Proceedings of the 27th Symposium on Computational Geometry (Paris, 2011) (ACM, New York, 2011), pp. 125–134
65.
B. Jackson, T. Jordán, Independence free graphs and vertex connectivity augmentation. J. Combin. Theor. Ser. B 94, 31–77 (2005)MATHCrossRef
66.
I.A. Kanj, L. Perkovic, G. Xia, On spanners and lightweight spanners of geometric graphs. SIAM J. Comput. 39(6), 2132–2161 (2010)MathSciNetMATHCrossRef
67.
G. Kant, Hexagonal grid drawings, in Proceedings of the 18th Workshop in Graph-Theoretic Concepts in Computer Science (WG’92), LNCS, vol. 657 (Springer-Verlag, Berlin, 1993), pp. 263–276
68.
G. Kant, H.L. Bodlaender, Planar graph augmentation problems, in Proceedings of the 2nd Workshop on Algorithms and Data Structures, vol. 519 of LNCS (Springer-Verlag, Berlin, 1991), pp. 286–298
69.
M. Kaufmann, R. Wiese, Embedding vertices at points: few bends suffice for planar graphs. J. Graph Algorithm. Appl. 6(1), 115–129 (2002)MathSciNetMATHCrossRef
70.
J.M. Keil, C.A. Gutwin, Classes of graphs which approximate the complete Euclidean graph. Discrete Comput. Geom. 7, 13–28 (1992)MathSciNetMATHCrossRef
71.
E. Kranakis, D. Krizanc, O. Morales, L. Stacho, Bounded length, 2-edge augmentation of geometric planar graphs, in Proceedings of the 4th Conference on Combinatorial Optimization and Applications, LNCS, vol. 6508 (Springer, Berlin, 2010), pp. 385–397
72.
M. Kurowski, A 1. 235 lower bound on the number of points needed to draw all n-vertex planar graphs. Inf. Proc. Lett. 92, 95–98 (2004)
73.
74.
A. Mirzaian, Hamiltonian triangulations and circumscribing polygons of disjoint line segments. Comput. Geom. Theor. Appl. 2(1), 15–30 (1992)MathSciNetMATHCrossRef
75.
H. Nagamochi, T. Ibaraki, Augmenting edge-connectivity over the entire range in O(nm) time. J. Algorithm. 30, 253–301 (1999)MathSciNetMATHCrossRef
76.
G. Narasimhan, M. Smid, Geometric Spanner Networks (Cambridge University Press, Cambridge, 2007)MATHCrossRef
77.
V. Neumann-Lara, E. Rivera-Campo, J. Urrutia, A note on convex decompositions of point sets in the plane. Graphs and Combinatorics 20(2), 223–231 (2004)
78.
M. Newborn, W.O.J. Moser, Optimal crossing-free Hamiltonian circuit drawings of K n . J. Combin. Theor. Ser. B 29, 13–26 (1980)MathSciNetCrossRef
79.
W. Mulzer, G. Rote, Minimum-weight triangulation is NP-hard. J. ACM 55(2), article 11 (2008)
80.
J. O’Rourke, Visibility, ed. by J.E. Goodman, J. O’Rourke. Handbook of Discrete and Computational Geometry, 2nd edn. (CRC Press, Boca Raton, FL, 2004), pp. 643–665
81.
J. O’Rourke, J. Rippel, Two segment classes with Hamiltonian visibility graphs. Comput. Geom. Theor. Appl. 4, 209–218 (1994)MathSciNetMATHCrossRef
82.
J. Pach, E. Rivera, Two segment classes with Hamiltonian visibility graphs. Comput. Geom. Theor. Appl. 10, 121–124 (1998)MATHCrossRef
83.
84.
D. Rappaport, Computing simple circuits from a set of line segments is NP-complete. SIAM J. Comput. 18(6), 1128–1139 (1989)MathSciNetMATHCrossRef
85.
D. Rappaport, H. Imai, G.T. Toussaint, Computing simple circuits from a set of line segments. Discrete Comput. Geom. 5(3), 289–304 (1990)MathSciNetMATHCrossRef
86.
87.
G. Rote, F. Santos, I. Streinu, in Pseudo-triangulations—A Survey, ed. by J.E. Goodman, J. Pach. Surveys on Discrete and Computational Geometry: Twenty Years Later, vol 453 of Contemporary Mathematics (AMS, Providence, RI, 2008), pp. 343–410
88.
T. Roughgarden, On the severity of Braess’s paradox: Designing networks for selfish users is hard. J. Comput. Syst. Sci. 72(5), 922–953 (2006)MathSciNetMATHCrossRef
89.
T. Roughgarden, in Routing Games, ed. by N. Nisan et al. Algorithmic Game Theory, Chapter 18 (Cambridge University Press, Cambridge, 2007)
90.
91.
J.R. Sack, J. Urrutia (eds.), Handbook of Computational Geometry (North Holland, Amsterdam, 2000)MATH
92.
T. Sakai, J. Urrutia, Convex decompositions of point sets in the plane, in Proceedings of the 7th Japan Conference on Computational Geometry and Graphs, JAIST, 2009
93.
W. Schnyder, Embedding planar graphs on the grid, in Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms, ACM Press. 1990, pp. 138–148
94.
M. Sharir, A. Sheffer, Counting triangulations of planar point sets. Electron. J. Combinat. 18, P70 (2011)MathSciNet
95.
M. Sharir, A. Sheffer, E. Welzl, Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn’s technique, in Proceedings of the 28th ACM Symposium on Computational Geometry, (ACM Press, 2012), pp. 189–198.
96.
M. Sharir, E. Welzl, On the number of crossing-free matchings (cycles, and partitions). SIAM J. Comput. 36(3), 695–720 (2006)MathSciNetMATHCrossRef
97.
98.
D.L. Souvaine, C.D. Tóth, A vertex-face assignment for plane graphs. Comput. Geom. Theor. Appl. 42(5), 388–394 (2009)MATHCrossRef
99.
I. Streinu, A combinatorial approach to planar non-colliding robot arm motion planning, in Proceedings of the 41st Symposium on Foundations of Computer Science (FoCS) (IEEE, Los Alamitos, CA, 2000), pp. 443–453
100.
101.
R. Tamassia (ed.), Handbook of Graph Drawing and Visualization CRC Press, 2013
102.
E. Tardos, T. Wexler, in Inefficiency of Equilibria in Network Formation Games, ed. by N. Nisan et al. Algorithmic Game Theory, Chapter 19 (Cambridge University Press, Cambridge, 2007)
103.
C.D. Tóth, Alternating paths along axis-parallel segments. Graphs Combinator. 22(4), 527–543 (2006)MATHCrossRef
104.
C.D. Tóth, Connectivity augmentation in planar straight line graphs. Europ. J. of Combinatorics, 33(3), 408–425 (2012)MATHCrossRef
105.
C.D. Tóth, P. Valtr, Augmenting the edge connectivity of planar straight line graphs to three, in Proceedings of the 13th Spanish Meeting on Computational Geomentry, Zaragoza, 2009
106.
107.
J. Urrutia, in Art Gallery and Illumination Problems, ed. by J.R. Sack, J. Urrutia. Handbook on Computational Geometry (Elsevier, Amsterdam, 2000), pp. 973–1127
108.
L. Végh, Augmenting undirected node-connectivity by one, in Proceedings of the 42nd Symposium on Theory of Computing (STOC) (ACM, New York, 2010), pp. 563–572
109.
110.
E. Welzl, The number of triangulations on planar point sets, in Proceedings of the 14th International Symposium (GD’06), LNCS, vol. 4372 (Springer, Berlin, 2007), pp. 1–4
111.
C. Wulff-Nilsen, Computing the dilation of edge-augmented graphs in metric spaces. Comput. Geom. Theor. Appl. 43, 68-72 (2010)MathSciNetMATHCrossRef
112.
G. Xia, Improved upper bound on the stretch factor of Delaunay triangulations, in Proceedings of the 27th Symposium on Computational Geomentry (SoCG) (ACM, New York, 2011), pp. 264–273
113.
G. Xia, L. Zhang, Improved lower bound for the stretch factor of Delaunay triangulations, in Proceedings of the 20th Fall Workshop on Computational Geomentry (Stony Brook, NY, 2010)
Metadaten
Titel
Plane Geometric Graph Augmentation: A Generic Perspective
verfasst von
Ferran Hurtado
Csaba D. Tóth
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_17