Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

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

  • Chapter
  • First Online:
Towards an Information Theory of Complex Networks

  • 1652 Accesses

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.

Nodes and edges are not assumed to be labeled.

MSC2000 Primary 05C10; Secondary 05C10, 05C30, 05C85.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

eBook
USD 15.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 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.

References

  1. Alonso, L., Rémy, J.L., Schott, R.: A linear-time algorithm for the generation of trees. Algorithmica 17(2), 162–182 (1997)

    Article  MathSciNet  Google Scholar 

  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)

    Chapter  Google Scholar 

  3. Barcucci, E., del Lungo, A., Pergola, E.: Random generation of trees and other combinatorial objects. Theor. Comput. Sci. 218(2), 219–232 (1999)

    Article  MathSciNet  Google Scholar 

  4. Bodirsky, M., Kang, M.: Generating random outerplanar graphs. In: 1st Workshop on Algorithms for Listing, Counting, and Enumeration (ALICE) (2003)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  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)

    Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  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)

    Google Scholar 

  12. Denise, A., Vasconcellos, M., Welsh, D.J.A.: The random planar graph. Congressus Numerantium 113, 61–79 (1996)

    Google Scholar 

  13. Diestel, R.: Graph Theory, 2nd edn., vol. 173 of Graduate Texts in Mathematics. Springer, New York (2000)

    Google Scholar 

  14. Epstein, P., Sack, J.R.: Generating triangulations at random. ACM Trans. Model. Comput. Simul. 4, 267–278 (1994)

    Article  Google Scholar 

  15. Frederickson, G.N., Janardan, R.: Efficient message routing in planar networks. SIAM J. Comput. 18(4), 843–857 (1989)

    Article  MathSciNet  Google Scholar 

  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)

    Google Scholar 

  17. Gerke, S., McDiarmid, C.J.H.: On the number of edges in random planar graphs. Combinator. Probab. Comput. 13, 165–183 (2004)

    Article  MathSciNet  Google Scholar 

  18. Giménez, O., Noy, M.: Asymptotic enumeration and limit laws of planar graphs. J. Am. Math. Soc. 22, 309–329 (2009)

    Article  MathSciNet  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  20. Keeler, K., Westbrook, J.: Short encodings of planar graphs and maps. Discrete Appl. Math. 58, 239–252 (1995)

    Article  MathSciNet  Google Scholar 

  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

    Google Scholar 

  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)

    Google Scholar 

  23. Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177–189 (1979)

    Article  MathSciNet  Google Scholar 

  24. Liskovets, V.A., Walsh, T.R.: Ten steps to counting planar graphs. Congressus Numerantium 60, 269–277 (1987)

    MathSciNet  MATH  Google Scholar 

  25. Liu, Y.: Enumeration of simple planar maps. Utilitas Math. 34, 97–104 (1988)

    MathSciNet  MATH  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  28. McDiarmid, C.J.H., Steger, A., Welsh, D.J.A.: Random planar graphs. J. Combin. Theor. B 93, 187–205 (2005)

    Article  MathSciNet  Google Scholar 

  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)

    Google Scholar 

  30. Nishizeki, T., Chiba, N.: Planar Graphs: Theory and Algorithms. North-Holland Mathematics Studies 140, Amsterdam (1988)

    Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  32. Pagh, R.: Low redundancy in static dictionaries with constant query time. SIAM J. Comput. 31(2), 353–363 (2001)

    Article  MathSciNet  Google Scholar 

  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)

    Chapter  Google Scholar 

  34. Rossignac, J.: Edgebreaker: Connectivity compression for triangle meshes. IEEE Trans. Visual. Comput. Graph. 5(1), 47–61 (1999)

    Article  MathSciNet  Google Scholar 

  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)

    Google Scholar 

  36. Schnyder, W.: Embedding planar graphs on the grid. In: 1st Symposium on Discrete Algorithms (SODA), pp. 138–148. ACM-SIAM (1990)

    Google Scholar 

  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)

    Google Scholar 

  38. Turán, G.: Succinct representations of graphs. Discrete Appl. Math. 8, 289–294 (1984)

    Article  MathSciNet  Google Scholar 

  39. Tutte, W.T.: A census of planar triangulations. Cana. J. Math. 14, 21–38 (1962)

    Article  MathSciNet  Google Scholar 

  40. Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Syst. Sci. 38, 36–67 (1989)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LaBRI, University of Bordeaux, 351 Cours de la libération, 33405, Bordeaux, France

    Nicolas Bonichon & Cyril Gavoille

  2. LaBRI, CNRS – University of Bordeaux, 351 Cours de la libération, 33405, Bordeaux, France

    Nicolas Hanusse

Authors
  1. Nicolas Bonichon
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Cyril Gavoille
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nicolas Hanusse
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nicolas Bonichon .

Editor information

Editors and Affiliations

  1. Medizinische Informatik und Technik, Institute for Bioinformatics and Transla, UMIT-Private Universität für Gesundheits, Eduard Wallnöfer-Zentrum 1, Hall in Tirol, A-6060, Austria

    Matthias Dehmer

  2. Queen's University Belfast, School of Medicine, Dentistry, and Cell, Center for Cancer Research & Cell Biolog, Lisburn Road 97, Belfast, BT97BL, United Kingdom

    Frank Emmert-Streib

  3. Goethe-University Frankfurt am Main, Department of Philosophy and Historical, Center for Computing in the Humanities, Senckenberganlage 31, Frankfurt, 60325, Germany

    Alexander Mehler

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer Science+Business Media, LLC

About this chapter

Cite this chapter

Bonichon, N., Gavoille, C., Hanusse, N. (2011). An Information-Theoretic Upper Bound on Planar Graphs Using Well-Orderly Maps. In: Dehmer, M., Emmert-Streib, F., Mehler, A. (eds) Towards an Information Theory of Complex Networks. Birkhäuser, Boston, MA. https://doi.org/10.1007/978-0-8176-4904-3_2

Download citation

Publish with us

Policies and ethics

Search

Navigation