Sampling Unlabeled 2-connected Planar Graphs
By Manuel Bodirsky, Clemens Gröpl, and Mihyun KangIn: Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC05), LNCS 3827, pages 593-603
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.
Deutsch