Repository: Freie Universität Berlin, Math Department

Decomposing, Counting, and Generating Unlabeled Cubic Planar Graphs

Bodirsky, M. and Gröpl, C. and Kang, M. (2003) Decomposing, Counting, and Generating Unlabeled Cubic Planar Graphs. In: European Conference on Combinatorics, Graph Theory, and Applications EUROCOMB'03 Prague.

Full text not available from this repository.


We present an expected polynomial time algorithm to generate an unlabeled connected cubic planar graph uniformly at random. We first consider rooted 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 3-connected 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 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 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.

Item Type:Conference or Workshop Item (UNSPECIFIED)
Uncontrolled Keywords:Cubic Planar Graph, Planar Graph, Cubic Graph, Enumeration, Random graphs, Random Generation, Dynamic Programming, Graph Theory
Subjects:Mathematical and Computer Sciences > Computer Science
Divisions:Department of Mathematics and Computer Science > Institute of Computer Science > Algorithmic Bioinformatics Group
ID Code:342
Deposited By: Admin Administrator
Deposited On:14 Apr 2009 14:36
Last Modified:14 Apr 2009 14:36

Repository Staff Only: item control page