
19.4. RANDOM MAP GENERATORS 609
19.4 Random Map Generators
Several polynomial-time random planar map uniform generators have been implemented by
Gilles Schaeffer in Pigale [Sch99]:
• planar maps (connected, 2-connected, or 3-connected),
• planar cubic maps (2-connected, 2-connected bipartite, 3-connected, 3-connected
bipartite, or dual-4-connected),
• planar 4-regular maps (2-connected, 3-connected, or bipartite),
• planar bipartite maps.
Also, linear-time uniform generators of outerplanar maps have been implemented by
Nicolas Bonichon [BGH03].
The implementation of these algorithms in Pigale uses the uniform pseudo-random num-
ber generator of Matsumoto ...