A Direct Decomposition of 3-connected Planar Graphs
By Manuel Bodirsky, Clemens Gröpl, Daniel Johannsen, and Mihyun KangSéminaire Lotharingien de Combinatoire, 54A (2007), Article B54Ak, 15 pp
Presented in the 17th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC05)
Part of Master's Thesis of Daniel Johannsen (3-connected Planar Graphs)
Abstract
We present a decomposition strategy for c-nets, i.e., rooted 3-connected planar maps. The decomposition yields an algebraic equation for the number of c-nets with a given number of vertices and a given size of the outer face. The decomposition also leads to a deterministic and polynomial time algorithm to sample c-nets uniformly at random. Using rejection sampling, we can also sample isomorphism types of convex polyhedra, i.e., 3-connected planar graphs, uniformly at random.
English