Efficient way to generate random planar cubic bipartite graphs

Question

3-regular bipartite planar graphs appear in a variety of NP- / #P-complete problems. Suppose one wants to test the complexity of these problems via numerical experiments. Is there an efficient way to generate random planar cubic bipartite graphs?

I only know of algorithms that can efficiently generate random graphs with only subsets of the set of properties {cubic,planar,bipartite}, and it seems that generating those and then naively testing for the remainder of the properties would be terribly inefficient if one wants graphs with >100 vertices.

Answer 1

Would you be satisfied with generating planar cubic bipartite maps (i.e., such graphs equipped with a planar embedding specified by a cyclic ordering on half-edges)? That problem was addressed in:

• Gilles Schaeffer, Bijective Census and Random Generation of Eulerian Planar Maps with Prescribed Vertex Degrees, The Electronic Journal of Combinatorics 4(1), 1997.

Schaeffer describes how to efficiently generate (rooted) Eulerian planar maps uniformly at random using a bijection with a certain family of trees. In turn, Eulerian maps have a simple bijection with bi(partite-)cubic maps: see the second bullet point on slide 5 of this talk by Éric Fusy.

(Generating a uniformly random rooted planar bicubic map and then throwing away the rooting + embedding would give you a non-uniform distribution on planar bicubic graphs, but depending on what you have in mind that might be okay?)

Answer 2

In case anyone else is looking for a practical answer: the program plantri by Brinkmann and McKay can generate small (up to 64 vertices as-is, up to 255 with some hacking) planar bipartite cubic graphs as the duals of Eulerian planar triangulations. The program does not sample uniformly at random, but it is claimed to be efficient enough to generate all small graphs in restricted families (e.g., 3-connected), so one could potentially generate them all first, then sample.