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

Counting Plane Graphs: Flippability and Its Applications

verfasst von : Michael Hoffmann, André Schulz, Micha Sharir, Adam Sheffer, Csaba D. Tóth, Emo Welzl

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 generalize the notions of flippable and simultaneously flippable edges in a triangulation of a set S of points in the plane to pseudo-simultaneously flippable edges. Such edges are related to the notion of convex decompositions spanned by S.
We prove a worst-case tight lower bound for the number of pseudo-simultaneously flippable edges in a triangulation in terms of the number of vertices. We use this bound for deriving new upper bounds for the maximal number of crossing-free straight-edge graphs that can be embedded on any fixed set of N points in the plane. We obtain new upper bounds for the number of spanning trees and forests as well. Specifically, let \(\mathsf{tr}(N)\) denote the maximum number of triangulations on a set of N points in the plane. Then we show [using the known bound \(\mathsf{tr}(N) < 3{0}^{N}\)] that any N-element point set admits at most \(6.928{3}^{N} \cdot \mathsf{tr}(N) < 207.8{5}^{N}\) crossing-free straight-edge graphs, \(O(4.702{2}^{N}) \cdot \mathsf{tr}(N) = O(141.0{7}^{N})\) spanning trees, and \(O(5.351{4}^{N}) \cdot \mathsf{tr}(N) = O(160.5{5}^{N})\) forests. We also obtain upper bounds for the number of crossing-free straight-edge graphs that have cN, fewer than cN, or more than cN edges, for any constant parameter c, in terms of c and N.

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 On Disjoint Crossing Families in Geometric Graphs
Nächstes Kapitel Plane Geometric Graph Augmentation: A Generic Perspective
Fußnoten
1
Up-to-date bounds for these and for other families of graphs can be found in http://​www.​cs.​tau.​ac.​il/​~sheffera/​counting/​PlaneGraphs.​html (version of November 2010).
 
2
In the notations O  ∗ (), \({\Theta }^{{_\ast}}()\), and \({\Omega }^{{_\ast}}()\), we neglect polynomial factors.
 
3
Here we implicitly assume that N is even. The case where N is odd is handled in the exact same manner, since a constant change in the size of F does not affect the asymptotic bounds.
 
4
This is not quite correct: When j is close to N ∕ 2, the former bound is smaller [e.g., it is O  ∗ (5 N ) for j = N ∕ 2], but we do not know how to exploit this observation to improve the bound.
 
5
We need to construct a quadrangulation of the annulus-like region between Q and the convex hull of S. We start by connecting a vertex of Q to a vertex of the convex hull, and in each step we add a quadrangle by either marching along two edges of the hull or along one edge of the hull and one edge of Q. This produces the desired quadrangulation.
 
Literatur
1.
O. Aichholzer, T. Hackl, C. Huemer, F. Hurtado, H. Krasser, B. Vogtenhuber, On the number of plane geometric graphs. Graphs Comb. 23(1), 67–84 (2007)MathSciNetMATHCrossRef
2.
M. Ajtai, V. Chvátal, M.M. Newborn, E. Szemerédi, Crossing-free subgraphs. Ann. Discr. Math. 12, 9–12 (1982)MATH
3.
4.
P. Bose, G. Toussaint, No quadrangulation is extremely odd, in Algorithms and Computations. Lecture Notes in Computer Science, vol. 1004 (Springer-Verlag, Berlin, 1995), pp. 372–381
5.
K. Buchin, C. Knauer, K. Kriegel, A. Schulz, R. Seidel, On the number of cycles in planar graphs, in Proceedings of the 17th Computing and Combinatorics Conference. Lecture Notes Computer Science, vol. 4598 (Springer, Berlin, 2007), pp. 97–107
6.
K. Buchin, A. Schulz, On the number of spanning trees a planar graph can have, in Proceedings of the 18th Annual European Symposium on Algorithms. Lecture Notes Computer Science, vol. 6346 (Springer, Berlin, 2010), pp. 110–121
7.
J.A. De Loera, J. Rambau, F. Santos, Triangulations: Structures for Algorithms and Applications (Springer, Berlin, 2010)MATH
8.
M.O. Denny, C.A. Sohler, Encoding a triangulation as a permutation of its point set, in Proceedings of the 9th Canadian Conference on Computational Geometry, 1997, Kingston, Ontario, Canada, pp. 39–43
9.
A. Dumitrescu, A. Schulz, A. Sheffer, Cs.D. Tóth, Bounds on the maximum multiplicity of some common geometric graphs, in Proceedings of the 28th Symposium on Theoretical Aspects of Computer Science, 2011, vol. 5 of LIPICS, Schloss Dagstuhl, Dagstuhl, pp. 637–648
10.
I. Fáry, On straight line representations of planar graphs. Acta Sci. Math. (Szeged) 11, 229–233 (1948)MATH
11.
12.
S. Fortune, Voronoi diagrams and Delaunay triangulations, in Computing in Euclidean Geometry, ed. by D.A. Du, F.K. Hwang (World Scientific, New York, 1992), pp. 193–233CrossRef
13.
J. Galtier, F. Hurtado, M. Noy, S. Pérennes, J. Urrutia, Simultaneous edge flipping in triangulations. Int. J. Comput. Geom. Appl. 13(2), 113–133 (2003)MATHCrossRef
14.
A. García, M. Noy, J. Tejel, Lower bounds on the number of crossing-free subgraphs of K N . Comput. Geom. Theor. Appl. 16(4), 211–221 (2000)MATHCrossRef
15.
J. García-Lopez, M. Nicolás, Planar point sets with large minimum convex partitions. Abstracts 22nd European Workshop on Computational Geometry, 2006, Delphi, Greece, pp. 51–54
16.
O. Giménez, M. Noy, Asymptotic enumeration and limit laws of planar graphs. J. Am. Math. Soc. 22, 309–329 (2009)MATHCrossRef
17.
Ø. Hjelle, M. Dæhlen, Triangulations and Applications (Springer, Berlin, 2009)
18.
19.
20.
L. Lovász, M. Plummer, Matching Theory (North Holland, Budapest, 1986)MATH
21.
22.
A. Razen, J. Snoeyink, E. Welzl, Number of crossing-free geometric graphs vs. triangulations. Electron. Notes Discr. Math. 31, 195–200 (2008)
23.
A. Ribó Mor, Realizations and counting problems for planar structures: trees and linkages, polytopes and polyominos. Ph.D. thesis, Freie Universität, Berlin, 2005
24.
G. Rote, The number of spanning trees in a planar graph. Oberwolfach Rep. 2, 969–973 (2005)
25.
F. Santos, R. Seidel, A better upper bound on the number of triangulations of a planar point set. J. Comb. Theor. Ser. A 102(1), 186–193 (2003)MathSciNetMATHCrossRef
26.
M. Sharir, A. Sheffer, Counting triangulations of planar point sets. Electron. J. Comb. 18(1), P70 (2011)MathSciNet
27.
M. Sharir, A. Sheffer, E. Welzl, On degrees in random triangulations of point sets. J. Comb. Theor. A 118, 1979–1999 (2011)MathSciNetMATHCrossRef
28.
M. Sharir, A. Sheffer, E. Welzl, Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn’s technique. Proc. 28th ACM Symp. on Computational Geometry, 2012, ACM, New York, pp. 189–198
29.
M. Sharir, E. Welzl, Random triangulations of planar point sets, in Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006, ACM, New York, pp. 273–281
30.
D.L. Souvaine, C.D. Tóth, A. Winslow, Simultaneously flippable edges in triangulations, in Proceedings of the XIV Spanish Meeting on Computational Geometry, 2011, Alcalá de Henares, Spain, pp. 137–140
31.
R.P. Stanley, Enumerative Combinatorics, vol. 2 (Cambridge University Press, Cambridge, 1999)CrossRef
32.
33.
J. Urrutia, Open problem session, in Proceedings of the 10th Canadian Conference on Computational Geometry, McGill University, Montréal, 1998
34.
K. Wagner, Bemerkungen zum Vierfarbenproblem. J. Deutsch. Math.-Verein. 46, 26–32 (1936)
Metadaten
Titel
Counting Plane Graphs: Flippability and Its Applications
verfasst von
Michael Hoffmann
André Schulz
Micha Sharir
Adam Sheffer
Csaba D. Tóth
Emo Welzl
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_16