Generating Labeled Planar Graph Uniformly at Random
By Manuel Bodirsky, Clemens Gröpl, Mihyun KangIn Proceedings of the Thirtieth International Colloquium on Automata, Languages and Programming (ICALP 2003), LNCS 2719, 1095 - 1107
Theoretical Computer Science, 379 (2007): 377-386
Abstract
We present a deterministic 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 Bodirsky, Gröpl, Johannsen, and Kang.Download
- ps - samplingplanar.ps
English