<p>In case anyone else is looking for a practical answer: the program <a href="https://users.cecs.anu.edu.au/~bdm/plantri/" rel="nofollow noreferrer" title="plantri">plantri</a> 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 <em>all</em> small graphs in restricted families (e.g., 3-connected), so one could potentially generate them all first, then sample.</p>

CC BY-SA 3.0
2018-02-01T14:02:42.353Z
2018-02-02T15:43:15.710Z
2018-02-02T15:43:15.710Z
delete000
<p>Would you be satisfied with generating planar cubic bipartite <em>maps</em> (i.e., such graphs equipped with a planar embedding specified by a cyclic ordering on half-edges)? That problem was addressed in:</p>

<ul>
<li>Gilles Schaeffer, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v4i1r20" rel="noreferrer">Bijective Census and Random Generation of Eulerian Planar Maps with Prescribed Vertex Degrees</a>, <em>The Electronic Journal of Combinatorics</em> 4(1), 1997.</li>
</ul>

<p>Schaeffer describes how to efficiently generate (rooted) <em>Eulerian planar maps</em> 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 <a href="http://www.labri.fr/perso/duchon/gtc/2007_09_07_Fusy.pdf" rel="noreferrer">this talk</a> by Éric Fusy.</p>

<p>(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?)</p>

CC BY-SA 3.0
2018-01-29T11:25:56.233Z
2018-01-29T11:25:56.233Z
Noam Zeilberger
<p>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?</p>

<p>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.</p>

<cc.complexity-theory><graph-theory><graph-algorithms><planar-graphs><bipartite-graphs>
Efficient way to generate random planar cubic bipartite graphs
delete000
# Efficient way to generate random planar cubic bipartite graphs

(Asked by: username_0 on 2018-01-28)

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.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, planar-graphs, bipartite-graphs


---

## 2 answers

### Answer by username_1 on 2018-01-29. Score: 7 | Accepted answer

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](http://www.combinatorics.org/ojs/index.php/eljc/article/view/v4i1r20), *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](http://www.labri.fr/perso/duchon/gtc/2007_09_07_Fusy.pdf) 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 by username_0 on 2018-02-01. Score: 3

In case anyone else is looking for a practical answer: the program [plantri](https://users.cecs.anu.edu.au/~bdm/plantri/ "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.


---

