Planar Graphs, via Well-Orderly Maps and Trees

1. Bonichon, N., Gavoille, C., Hanusse, N.: An information upper bound of planar graphs using triangulation. Research Report RR-1279-02, LaBRI, University of Bordeaux, 351, cours de la Libération, 33405 Talence Cedex, France, September 2002

2. 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), volume 2607 of Lecture Notes in Computer Science, pages 499–510. Springer, February 2003

3. Bodirsky, M., Gröpl, C., Kang, M.: Generating labeled planar graphs uniformly at random. In: 30th International Colloquium on Automata, Languages and Programming (ICALP), volume 2719 of LNCS, pages 1095–1107, 2003

4. Bender, E.A., Gao, Z., Wormald, N.C.: The number of labeled 2-connected planar graphs. The Electronic Journal of Combinatorics 9(1), R43 (2002)

5. Bonichon, N., Le Saëc, B., Mosbah, M.: Optimal area algorithm for planar polyline drawings. In: 28th International Workshop, Graph - Theoretic Concepts in Computer Science (WG), volume 2573 of LNCS, pages 35–46. Springer, 2002

6. Bonichon, N., Le Saëc, B., Mosbah, M.: Wagner's theorem on realizers. In: 29th International Colloquium on Automata, Languages and Programming (ICALP). volume 2380 of LNCS, pages 1043–1053. Springer, 2002

7. Bonichon, N.: A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths. In: Formal Power Series & Algebraic Combinatorics (FPSAC). July 2002

8. Chih-Nan Chuang, R., Garg, A., He X., Kao M.-Y., Lu H.-I.: Compact encodings of planar graphs via canonical orderings and multiple parentheses. In: 25th International Colloquium on Automata, Languages and Programming (ICALP), volume 1443 of LNCS, pages 118–129. Springer, July 1998

9. 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), pages 506–515. ACM-SIAM, January 2001

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

    Google Scholar 

11. Frederickson, G. N., Janardan, R.: Efficient message routing in planar networks. SIAM Journal on Computing, 18(4), 843–857, August (1989)

    Google Scholar 

12. Flajolet, P., Sedgewick,R.: Analytic combinatorics. Future book available online at the URL http://algo.inria.fr/flajolet/Publications/books.html

13. Gavoille, C., Hanusse, N.: Compact routing tables for graphs of bounded genus. In: 26^th International Colloquium on Automata, Languages and Programming (ICALP), volume 1644 of LNCS, pages 351–360. Springer, July 1999

14. Goulden, I. P., Jackson, D. M.: Combinatorial Enumeration. John Wiley & Sons, 1983

15. Gerke, S., McDiarmid, C. J. H.: On the number of edges in random planar graphs. Combinatorics, Probability & Computing, 2002 (to appear)

16. Giménez, O., Noy, M.: Asymptotic enumeration and limit laws of planar graphs. preprint arXiv:Math.CO/051269

17. Khodakovsky, A., Alliez, P., Desbrun, M. Schröder, P.: Near-optimal connectivity encoding of 2-manifold polygon meshes. Graphical Models, 2002. To appear in a special issue

18. King, D., Rossignac, J.: Guaranteed 3.67V bit encoding of planar triangle graphs. In: 11^th Canadian Conference on Computational Geometry. pp 146–149, August 1999

19. Keeler, K. Westbrook, J.: Short encodings of planar graphs and maps. Discrete Applied Mathematics 58, 239–252 (1995)

    Google Scholar 

20. Lu, H.-I.: Improved compact routing tables for planar networks via orderly spanning trees. In: 8^th Annual International Computing & Combinatorics Conference (COCOON), volume 2387 of LNCS, pages 57–66. Springer, August 2002

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

    Google Scholar 

22. Munro, J. I., Raman, V.: Succinct representation of balanced parentheses, static trees and planar graphs. In: 38^th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 118–126. IEEE Computer Society Press, October 1997

23. McDiarmid, C., Steger, A., Welsh, D. J. A.: Random planar graphs. J. Comb. Theory Ser. B 93(2), 187–205 (2005)

    Google Scholar 

24. Osthus, D., Prömel, H. J., Taraz, A.: On random planar graphs, the number of planar graphs and their triangulations. Journal of Combinatorial Theory, Series B 88, 119–134 (2003)

    Google Scholar 

25. Poulalhon, D., Schaeffer, G.: Optimal coding and sampling of triangulations. In: 30^th International Colloquium on Automata, Languages and Programming (ICALP), volume 2719 of LNCS, pages 1080–1094. Springer, July 2003

26. Rossignac, J.: Edgebreaker: Connectivity compression for triangle meshes. IEEE Transactions on Visualization and Computer Graphics 5(1), 47–61 (1999)

    Google Scholar 

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

28. Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. In 42^th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, October 2001.

29. Turán, G.: Succinct representations of graphs. Discrete Applied Mathematics 8, 289–294 (1984)

    Google Scholar 

30. Tutte, W. T.: A census of planar triangulations. Canadian Journal of Mathematics 14, 21–38 (1962)

    Google Scholar 

31. Wright, E. M.: Graphs on unlabelled nodes with a given number of edges. Acta Math. 126, 1–9 (1971)

    Google Scholar 

32. Yannakakis, M.: Embedding planar graphs in four pages. Journal of Computer and System Sciences 38, 36–67 (1989)

    Google Scholar 

33. Zhang, H., He, X.: Compact visibility representation and straight-line grid embedding of plane graphs. In: Workshop on Algorithms and Data Structures (WADS), volume 2748 of LNCS, pages 493–504. Springer, July 2003

Download references