With Clemens Gröpl and Mihyun Kang. Accepted for publication in the special issue of Theoretical Computer Science (TCS) on the Thirtieth International Colloquium on Automata, Languages and Programming (ICALP 2003), LNCS 2719, 1095 - 1107.
Abstract
We present an expected polynomial time algorithm to generate a labeled planar graph uniformly at random. To generate the planar graphs, we derive recurrence formulas that count all such graphs with n vertices and m edges, based on a decomposition into 1-, 2-, and 3-connected components. For 3-connected graphs we apply a recent random generation algorithm by Schaeffer and a counting formula by Mullin and Schellenberg.
Download
Postscript (preliminary version)
