Abstract
We propose a new linear time algorithm to represent a planar graph. Based on a specific triangulation of the graph, our coding takes on average 5.03 bits per node, and 3.37 bits per node if the graph is maximal. We derive from this representation that the number of unlabeled planar graphs with n nodes is at most 2∞n+O(log n), where ∞≈5.007. The current lower bound is 2βn+ø(log n) for β≈4.71. We also show that almost all unlabeled and almost all labeled n-node planar graphs have at least 1.70n edges and at most 2.54n edges.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. Alonso, J. L. Rémy, and R. Schott. A linear-time algorithm for the generation of trees. Algorithmica, 17(2):162–182, 1997.
C. Banderier, P. Flajolet, G. Schaeffer, and M. Soria. Planar maps and airy phenomena.In 27th ICALP, vol. 1853 of LNCS, pp. 388–402. Springer, Jul. 2000.
E. Barcucci, A. del Lungo, and E. Pergola. Random generation of trees and other combinatorial objects. Theoretical Computer Science, 218(2):219–232, 1999.
E.A. Bender, Z. Gao, and N.C. Wormald. The number of labeled 2-connected planar graphs, 1999. Manuscript.
M. Bodirsky and M. Kang. Generating random outerplanar graphs. In ALICE’ 03.
B. Bollobás. Extremal Graph Theory. Academic Press, New York, 1978.
N. Bonichon. A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths. In FPSAC, Jul. 2002.
N. Bonichon, C. Gavoille, and N. Hanusse. An information upper bound of planar graphs using triangulation. TR #1279-02, LaBRI, Univ. of Bordeaux, Sep. 2002.
M. Bousquet-Mélou, 2002. Private communication.
Y.-T. Chiang, C.-C. Lin, and H.-I Lu. Orderly spanning trees with applications to graph encoding and graph drawing. In 12th SODA, pp. 506–515, Jan. 2001.
N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa. A linear algorithm for embedding planar graphs using pq-trees. J. of Comp. and Sys. Sci., 30(1):54–76, 1985.
R.C.-N. Chuang, A. Garg, X. He, M.-Y. Kao, and H.-I Lu. Compact encodings of planar graphs via canonical orderings and multiple parentheses. In 25th ICALP, vol. 1443 of LNCS, pp. 118–129. Springer, Jul. 1998.
A. Denise, M. Vasconcellos, and D.J.A. Welsh. The random planar graph. Congressus Numerantium, 113:61–79, 1996.
R. Diestel. Graph Theory, vol. 173 of Graduate Texts in Math. Springer, 2000.
P. Epstein and J.-R. Sack. Generating triangulations at random. ACM Trans. Model. and Comput. Simul.,4:267–278, 1994.
G.N. Frederickson and R. Janardan. Efficient message routing in planar networks. SIAM J. on Computing, 18(4):843–857, August 1989.
C. Gavoille and N. Hanusse. Compact routing tables for graphs of bounded genus. In 26th ICALP, vol. 1644 of LNCS, pp. 351–360. Springer, Jul. 1999.
S. Gerke and C. McDiarmid. Adding edges to planar graphs, 2001. Preprint.
X. He, M.-Y. Kao, and H.-I Lu. A fast general methodology for informationtheoretically optimal encodings of graphs. SIAM J. on Comp., 30:838–846, 2000.
K. Keeler and J. Westbrook. Short encodings of planar graphs and maps. Discr. Appl. Math., 58:239–252, 1995.
A. Khodakovsky, P. Alliez, M. Desbrun, and P. Schröder. Near-optimal connectivity encoding of 2-manifold polygon meshes. Graphical Models, 2002. To appear.
D. King and J. Rossignac. Guaranteed 3.67V bit encoding of planar triangle graphs. In 11th CCCG, pp. 146–149, Aug. 1999.
Y. Liu. Enumeration of simple planar maps. Util. Math., 34:97–104, 1988.
R.J. Lipton and R.E. Tarjan. A separator theorem for planar graphs. SIAM J. on Applied Mathematics, 36(2):177–189, Apr. 1979.
V.A. Liskovets and T.R. Walsh. Ten steps to counting planar graphs. Congressus Numerantium, 60:269–277, 1987.
H.-I Lu. Improved compact routing tables for planar networks via orderly spanning trees. In 8th COCOON, vol. 2387 of LNCS, pp. 57–66. Springer, Aug. 2002.
H.-I Lu. Linear-time compression of bounded-genus graphs into informationtheoretically optimal number of bits. In 13th SODA, pp. 223–224, Jan. 2002.
J.I. Munro and V. Raman. Succinct representation of balanced parentheses, static trees and planar graphs. In 38th FOCS, pp. 118–126. IEEE Press, 1997.
D. Osthus, H.J. Prömel, and A. Taraz. On random planar graphs, the number of planar graphs and their triangulations. Submitted for publication, 2002.
R. Pagh. Low redundancy in static dictionaries with constant query time. SIAM J. on Computing, 31(2):353–363, 2001.
J. Rossignac. Edgebreaker: Connectivity compression for triangle meshes. IEEE Transactions on Visualization and Computer Graphics, 5(1):47–61, 1999.
G. Schaeffer. Random sampling of large planar maps and convex polyhedra. In 31st STOC, pp. 760–769, May 1999.
W. Schnyder. Embedding planar graphs on the grid. In SODA’ 90, pp. 138–148.
M. Thorup. Compact oracles for reachability and approximate distances in planar digraphs. In 42th FOCS. IEEE Computer Society Press, Oct. 2001.
G. Turán. Succinct representations of graphs. Discr. Appl. Math., 8:289–294, 1984.
W.T. Tutte. A census of planar triangulations. Can. J. of Math., 14:21–38, 1962.
M. Yannakakis. Embedding planar graphs in four pages. J. of Comp. and Sys. Sci., 38:36–67, 1989.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bonichon, N., Gavoille, C., Hanusse, N. (2003). An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation. In: Alt, H., Habib, M. (eds) STACS 2003. STACS 2003. Lecture Notes in Computer Science, vol 2607. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36494-3_44
Download citation
DOI: https://doi.org/10.1007/3-540-36494-3_44
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00623-7
Online ISBN: 978-3-540-36494-8
eBook Packages: Springer Book Archive