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:
Entropy of Digraphs and Infinite Networks Kapitel lesen Erstes Kapitel lesen

2011 | OriginalPaper | Buchkapitel

2. An Information-Theoretic Upper Bound on Planar Graphs Using Well-Orderly Maps

verfasst von : Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse

Erschienen in: Towards an Information Theory of Complex Networks

Verlag: Birkhäuser Boston

Einloggen

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

search-config
loading …

Abstract

This chapter deals with compressed coding of graphs. We focus on planar graphs, a widely studied class of graphs. A planar graph is a graph that admits an embedding in the plane without edge crossings. Planar maps (class of embeddings of a planar graph) are easier to study than planar graphs, but as a planar graph may admit an exponential number of maps, they give little information on graphs. In order to give an information-theoretic upper bound on planar graphs, we introduce a definition of a quasi-canonical embedding for planar graphs: well-orderly maps. This appears to be an useful tool to study and encode planar graphs. We present upper bounds on the number of unlabeled1 planar graphs and on the number of edges in a random planar graph. We also present an algorithm to compute well-orderly maps and implying an efficient coding of planar graphs.

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 Entropy of Digraphs and Infinite Networks
Nächstes Kapitel Probabilistic Inference Using Function Factorization and Divergence Minimization
Fußnoten
1
The original compressor runs in expected linear time. We give in this chapter a simpler guaranteed linear time construction with asymptotically the same performances.
 
Literatur
1.
Alonso, L., Rémy, J.L., Schott, R.: A linear-time algorithm for the generation of trees. Algorithmica 17(2), 162–182 (1997)MathSciNetCrossRef
2.
Banderier, C., Flajolet, P., Schaeffer, G., Soria, M.: Planar maps and airy phenomena. In: 27th International Colloquium on Automata, Languages and Programming (ICALP), vol. 1853 of Lecture Notes in Computer Science, pp. 388–402. Springer, New York (2000)CrossRef
3.
Barcucci, E., del Lungo, A., Pergola, E.: Random generation of trees and other combinatorial objects. Theor. Comput. Sci. 218(2), 219–232 (1999)MathSciNetCrossRef
4.
Bodirsky, M., Kang, M.: Generating random outerplanar graphs. In: 1st Workshop on Algorithms for Listing, Counting, and Enumeration (ALICE) (2003)
5.
Bonichon, N.: A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths. In: Formal Power Series & Algebraic Combinatorics (FPSAC) (2002)
6.
Bonichon, N., Gavoille, C., Hanusse, N.: An information-theoretic upper bound of planar graphs using triangulation. In: 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), vol. 2607 of Lecture Notes in Computer Science, pp. 499–510. Springer, New York (2003)
7.
Bonichon, N., Gavoille, C., Hanusse, N., Poulalhon, D., Schaeffer, G.: Planar graphs, via well-orderly maps and trees. Graph. Combinator. 22, 1–18 (2006)MathSciNetCrossRef
8.
Chiang, Y.T., Lin, C.C., Lu, H.I.: Orderly spanning trees with applications to graph encoding and graph drawing. In: 12th Symposium on Discrete Algorithms (SODA), pp. 506–515. ACM-SIAM (2001)
9.
Chiba, N., Nishizeki, T., Abe, S., Ozawa, T.: A linear algorithm for embedding planar graphs using pq-trees. J. Comput. Syst. Sci. 30(1), 54–76 (1985)MathSciNetCrossRef
10.
Chiba, N., Nishizeki, T., Abe, S., Ozawa, T.: A linear algorithm for embedding planar graphs using pq-trees. J. Comput. Syst. Sci. 30(1), 54–76 (1985)MathSciNetCrossRef
11.
Chuang, R.C.N., Garg, A., He, X., Kao, M.Y., Lu, H.I.: Compact encodings of planar graphs via canonical orderings and multiple parentheses. In: Guldstrand Larsen, K., Skyum, S., Winskel, G. (eds.) 25th International Colloquium on Automata, Languages and Programming (ICALP), vol. 1443 of Lecture Notes in Computer Science, pp. 118–129. Springer, New York (1998)
12.
Denise, A., Vasconcellos, M., Welsh, D.J.A.: The random planar graph. Congressus Numerantium 113, 61–79 (1996)
13.
Diestel, R.: Graph Theory, 2nd edn., vol. 173 of Graduate Texts in Mathematics. Springer, New York (2000)
14.
Epstein, P., Sack, J.R.: Generating triangulations at random. ACM Trans. Model. Comput. Simul. 4, 267–278 (1994)CrossRef
15.
Frederickson, G.N., Janardan, R.: Efficient message routing in planar networks. SIAM J. Comput. 18(4), 843–857 (1989)MathSciNetCrossRef
16.
Gavoille, C., Hanusse, N.: Compact routing tables for graphs of bounded genus. In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) 26th International Colloquium on Automata, Languages and Programming (ICALP), vol. 1644 of Lecture Notes in Computer Science, pp. 351–360. Springer, New York (1999)
17.
Gerke, S., McDiarmid, C.J.H.: On the number of edges in random planar graphs. Combinator. Probab. Comput. 13, 165–183 (2004)MathSciNetCrossRef
18.
Giménez, O., Noy, M.: Asymptotic enumeration and limit laws of planar graphs. J. Am. Math. Soc. 22, 309–329 (2009)MathSciNetCrossRef
19.
He, X., Kao, M.Y., Lu, H.I.: A fast general methodology for information-theoretically optimal encodings of graphs. SIAM J. Comput. 30(3), 838–846 (2000)MathSciNetCrossRef
20.
Keeler, K., Westbrook, J.: Short encodings of planar graphs and maps. Discrete Appl. Math. 58, 239–252 (1995)MathSciNetCrossRef
21.
Khodakovsky, A., Alliez, P., Desbrun, M., Schröder, P.: Near-optimal connectivity encoding of 2-manifold polygon meshes. Graph. Model. (2002). To appear in a special issue
22.
King, D., Rossignac, J.: Guaranteed 3.67V bit encoding of planar triangle graphs. In: 11th Canadian Conference on Computational Geometry (CCCG), pp. 146–149 (1999)
23.
Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177–189 (1979)MathSciNetCrossRef
24.
Liskovets, V.A., Walsh, T.R.: Ten steps to counting planar graphs. Congressus Numerantium 60, 269–277 (1987)MathSciNetMATH
25.
26.
Lu, H.I.: Improved compact routing tables for planar networks via orderly spanning trees. In: 8th Annual International Computing & Combinatorics Conference (COCOON), vol. 2387 of Lecture Notes in Computer Science, pp. 57–66. Springer, New York (2002)
27.
Lu, H.I.: Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits. In: 13th Symposium on Discrete Algorithms (SODA), pp. 223–224. ACM-SIAM (2002)
28.
29.
Munro, J.I., Raman, V.: Succinct representation of balanced parentheses, static trees and planar graphs. In: 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 118–126. IEEE Computer Society Press (1997)
30.
Nishizeki, T., Chiba, N.: Planar Graphs: Theory and Algorithms. North-Holland Mathematics Studies 140, Amsterdam (1988)
31.
Osthus, D., Prömel, H.J., Taraz, A.: On random planar graphs, the number of planar graphs and their triangulations. J. Combin. Theor. B 88, 119–134 (2003)MathSciNetCrossRef
32.
Pagh, R.: Low redundancy in static dictionaries with constant query time. SIAM J. Comput. 31(2), 353–363 (2001)MathSciNetCrossRef
33.
Poulalhon, D., Schaeffer, G.: Optimal coding and sampling of triangulations. In: 30th International Colloquium on Automata, Languages and Programming (ICALP), vol. 2719 of Lecture Notes in Computer Science, pp. 1080–1094. Springer, New York (2003)CrossRef
34.
Rossignac, J.: Edgebreaker: Connectivity compression for triangle meshes. IEEE Trans. Visual. Comput. Graph. 5(1), 47–61 (1999)MathSciNetCrossRef
35.
Schaeffer, G.: Random sampling of large planar maps and convex polyhedra. In: 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 760–769 (1999)
36.
Schnyder, W.: Embedding planar graphs on the grid. In: 1st Symposium on Discrete Algorithms (SODA), pp. 138–148. ACM-SIAM (1990)
37.
Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. In: 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 242–251. IEEE Computer Society Press (2001)
38.
39.
40.
Metadaten
Titel
An Information-Theoretic Upper Bound on Planar Graphs Using Well-Orderly Maps
verfasst von
Nicolas Bonichon
Cyril Gavoille
Nicolas Hanusse
Copyright-Jahr
2011
Verlag
Birkhäuser Boston
Buch
Towards an Information Theory of Complex Networks

Print ISBN: 978-0-8176-4903-6

Electronic ISBN: 978-0-8176-4904-3

Copyright-Jahr: 2011

DOI
https://doi.org/10.1007/978-0-8176-4904-3_2