Efficient way to generate random planar cubic bipartite graphs 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.
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?)