Abstract
We present an expected polynomial time algorithm to generate a 2-connected unlabeled planar graph uniformly at random. To do this we first derive recurrence formulas to count the exact number of rooted 2-connected planar graphs, based on a decomposition along the connectivity structure. For 3-connected planar graphs we use the fact that they have a unique embedding on the sphere. Special care has to be taken for rooted graphs that have a sense-reversing or a pole-exchanging automorphism. We prove a bijection between such symmetric objects and certain colored networks. These colored networks can again be decomposed along their connectivity structure. All the numbers can be evaluated in polynomial time by dynamic programming. To generate 2-connected unlabeled planar graphs without a root uniformly at random we apply rejection sampling and obtain an expected polynomial time algorithm.
This is a preview of subscription content, log in via an institution to check access.
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
Banderier, C., Flajolet, P., Schaeffer, G., Soria, M.: Random maps, coalescing saddles, singularity analysis, and Airy phenomena. Random Structures and Algorithms 19, 194–246 (2001)
Bender, A., Gao, Z., Wormald, N.: The number of labeled 2-connected planar graphs. Electronic Journal of Combinatorics 9(43) (2002)
Bender, E.A., Wormald, N.: Almost all convex polyhedra are asymmetric. Can. J. Math. 27(5), 854–871 (1985)
Bodirsky, M., Giménez, O., Kang, M., Noy, M.: On the number of series-parallel and outerplanar graphs. In: The Proceedings of European Conference on Combinatorics, Graph Theory, and Applications (EuroComb 2005). DMTCS Proceedings Series Volume AE, pp. 383–388 (2005)
Bodirsky, M., Gröpl, C., Johannsen, D., Kang, M.: A direct decomposition of 3-connected planar graphs. In: Proceedings of the 17th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2005), Taormina (2005)
Bodirsky, M., Gröpl, C., Kang, M.: Sampling unlabeled biconnected planar graphs, Full version, available at http://www.informatik.hu-berlin.de/Forschung_Lehre/algorithmen/en/forschung/planar/
Bodirsky, M., Gröpl, C., Kang, M.: Generating labeled planar graphs uniformly at random. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 1095–1107. Springer, Heidelberg (2003)
Bodirsky, M., Kang, M.: Generating outerplanar graphs uniformly at random. Accepted for publication in Combinatorics, Probability and Computing. Presented at the 1st workshop on Algorithms for Listing, Counting, and Enumeration, ALICE 2003 (2003)
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 (2003)
Denise, A., Vasconcellos, M., Welsh, D.: The random planar graph. Congressus Numerantium 113, 61–79 (1996)
Denise, A., Zimmermann, P.: Uniform random generation of decomposable structures using floating-point arithmetic. Theoretical Computer Science 218, 233–248 (1999)
Diestel, R.: Graph Theory. Springer, New York (1997)
Eric Fusy, D.P., Schaeffer, G.: Dissections and trees: applications to optimal mesh encoding and random sampling. In: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (SODA 2005), pp. 690–699 (2005)
Flajolet, P., Zimmerman, P., Van Cutsem, B.: A calculus for the random generation of labelled combinatorial structures. Theoretical Computer Science 132(1-2), 1–35 (1994)
Gerke, S., McDiarmid, C.: On the number of edges in random planar graphs. Comb. Prob. and Computing 13, 358–402 (2004)
Giménez, O., Noy, M.: Asymptotic enumeration and limit laws of planar graphs (preprint)
Hopcroft, J.E., Wong, J.K.: Linear time algorithm for isomorphism of planar graphs. In: Annual ACM Symposium on Theory of Computing, pp. 172–184 (1974)
McDiarmid, C., Steger, A., Welsh, D.: Random planar graphs. Journal of Combinatorial Theory, Series B 93, 187–205 (2005)
Nijenhuis, A., Wilf, H.: Combinatorial algorithms. Academic Press Inc., London (1979)
Osthus, D., Prömel, H.J., Taraz, A.: On random planar graphs, the number of planar graphs and their triangulations. J. Combinatorial Theory, Series B, 119–143 (2003)
Schaeffer, G.: Random sampling of large planar maps and convex polyhedra. In: Proc. of the Thirty-first Annual ACM Symposium on the Theory of Computing (STOC 1999), Atlanta, Georgia, May 1999, pp. 760–769 (1999)
Steinitz, E.: Polyeder und Raumeinteilungen. Encyclopädie der mathematischen Wissenschaften Band III(9) (1922)
Trakhtenbrot, B.A.: Towards a theory of non-repeating contact schemes. Trudi Mat. Inst. Akad. Nauk SSSR 51, 226–269 (1958) (in Russian)
Tutte, W.T.: Graph Theory. Cambridge University Press, Cambridge (1984)
Walsh, T.: Counting labelled three-connected and homeomorphically irreducible two-connected graphs. J. Combin. Theory 32, 1–11 (1982)
Walsh, T., Liskovets, V.A.: Ten steps to counting planar graphs. In: 18th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Congr. Numer., vol. 60, pp. 269–277 (1987)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bodirsky, M., Gröpl, C., Kang, M. (2005). Sampling Unlabeled Biconnected Planar Graphs. In: Deng, X., Du, DZ. (eds) Algorithms and Computation. ISAAC 2005. Lecture Notes in Computer Science, vol 3827. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11602613_60
Download citation
DOI: https://doi.org/10.1007/11602613_60
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30935-2
Online ISBN: 978-3-540-32426-3
eBook Packages: Computer ScienceComputer Science (R0)