Generating Unlabeled Connected Cubic Planar Graphs Uniformly at Random
By Manuel Bodirsky, Clemens Gröpl, and Mihyun KangRandom Structures and Algorithms, 34 (2008), 157-180
Journal version of the extented abstract Decomposing, Counting, and Generating Unlabeled Cubic Planar Graphs in the Proceedings of the European Conference on Combinatorics, Graph Theory, and Applications (EUROCOMOB 2003)
Abstract
We present an expected polynomial time algorithm to generate an
unlabeled connected cubic planar graph uniformly at random. We
first consider rooted
connected cubic planar graphs,
i.e., we count connected cubic planar
graphs up to isomorphisms that fix a certain directed edge. Based on
decompositions along the connectivity structure, we derive recurrence
formulas for counting the exact number of rooted cubic planar graphs.
This leads to rooted 3-connected cubic planar graphs, which have a
unique embedding on the sphere; but special care has to be taken for
rooted graphs that have a sense-reversing
automorphism. Therefore we introduce the concept of colored networks, which
stand in bijective correspondence to rooted 3-connected cubic planar
graphs with given symmetries. Colored networks can again be decomposed
along their connectivity structure.
For rooted 3-connected cubic planar graphs embedded in the plane, we
switch to the dual and count rooted triangulations.
All these numbers can be evaluated in polynomial time by dynamic programming. We can use them to generate rooted connected cubic planar graphs uniformly at random. To generate connected cubic planar graphs without a root uniformly at random, we apply rejection sampling and obtain an expected polynomial time algorithm.
Download
- ps - unlcubicplanar.ps
- pdf - unlcubicplanar.pdf
