Random planar, bipartite graphs

Question

I have a need to generate random planar graphs none of which have an odd cycle, i.e., bipartite graphs. I know there is a substantial two-decade literature on random planar graphs, little with which I am familiar. I know there are several models: at least those that specify an edge probability, those that depend on a random graph process, and uniform random planar graphs. I am wondering if those familiar with these and other models could suggest one that might be modified to generate even-cycled planar graphs. I don't have strict distribution requirements—randomness in any one of several senses would suffice. Thanks for your advice!

---

I should have added the only two ideas I had, neither of which I feel is adequate, even under a loose definition of "random":

• Generate a random planar graph, and add a vertex in the middle of each edge. Then all these newly added vertices have degree $2$.
• Select out a random subgraph of the grid graph. Then no vertex has degree greater than $4$.

Answer 1

First make a "random" quadrangulation, then take a random subgraph of that. Since every planar bipartite graph can be made into a quadrangulation by adding edges, at least you know that every outcome is possible (though perhaps far from equally probable).

To make a "random" quadrangulation, start with a square then repeatedly choose a path of length 2 (randomly, of course) and open it up into a new square. Keep doing that until it is large enough.

Another thing you can do is wander around in the class of quadrangulations by diagonal flips. Given a quadrangulation, remove an edge (making a face of size 6) and reinsert it in one of the other two diagonals of the new 6-face. Do this lots of times. If you don't mind multiple edges, this can probably be made into a Markov chain on labelled quadrangulations that has a uniform distribution in the limit. If you do mind multiple edges, you can either avoid making them or you can just suppress them at the end.

You can also do random walks akin to diagonal flipping in more general planar bipartite graphs. Just remove an edge then put it back in some other place that makes a bipartite graph. Doing this lots of times starting at an arbitrary graph will give you something pretty random-ish.

Answer 2

A further approach starts with a random geometric graph (RGG): Assign a domain $D\subset\mathbb{R}^2$, typically a square. Place points using a Poisson process and make links between pairs less than a distance $r$ apart.

Then, colour the points randomly with two colours and delete links between points of the same colour to make the graph bipartite. Then, delete the longest link that intersects another (drawing straight lines between the points) recursively until there are no intersections and the graph is planar.

My interest in RGGs comes from their application to wireless networks (eg arxiv:1401.7188 and references therein); not sure if planar bipartite RGGs have such an application, but in any case it's an interesting question.

Answer 3

Use whatever random planar graph sampler to get a planar graph with blue vertices. Put a red vertex on each edge.

Answer 4

My recipe would be to
1. generate a random set of points in the plane,
2. select an arbitrary point of that set as a reference
3. calculate an arbitrary planar spanning tree
4. set the color of all vertices to $white$
5. set to $black$ the color of all vertices, that can be reached from the reference vertex via an even number of tree-edges.
6. randomly insert .edges that connect vertices of different color and that do not intersect a previously inserted edge (including the tree-edges) until the graph is saturated or until a previously chosen number of edges has been inserted into the graph.

The generation of such graphs can somewhat be speeded up by taking the minimum spanning tree as the spanning tree and the Delaunay triangulation as the triangulation, from which then all edges are removed that are adjacent to vertices of equal color.
.If the graph still contains more edges than desired, continue with deleting randomly selected edges.

Answer 5

The most general method would be to successively expand a connected, planar, bipartite graph $G$, whose vertices are colored $purple$ and $orange$ in a manner that makes each edge adjacent to a $purple$ and an $orange$ vertex.
In every step, $G$ can be expanded by either:

• adding a vertex that is connected to $G$ via an edge and colored in a way that makes the newly added edge adjacent to two different colors

or

• by adding adding an edge not yet in the graph that would connect vertices of different color and, that would preserve planarity.

As the planarity of graphs can be checked efficiently, (see e.g. http://en.wikipedia.org/wiki/Planarity_testing) it is viable to determine in each step a set of candidate edges, whose insertion into $G$ would preserve planarity; the bipartitness is ensured by inserting only edges that would connect vertices of different color.

A basic, purely "topological" method could then be to expand the graph by first checking if the set of candidate edges for insertion, while preserving planarity and bipartitness, is empty;

if that is the case, the only option is to

• add a new vertex to the graph, restore the graph's connectivity via a single edge and color the newly added vertex appropriately

• update the set of candidate edges by adding to it those edges that would be adjacent to the newly added vertex and, adjacent to another vertex of different color.

else roll dice whether to expand the graph via adding a new vertex as described above or whether to

• add a randomly selected edge from the candidate set and to

• redetermine the set of candidate edges by removing from it those edges, whose insertion would violate the planarity condition.

The selection of the vertex, to which a new vertex will be connected, or, which of the candidate edges will be selected, can e.g. be controlled by probabilities that depend on vertex degrees; also the decision whether to add a vertex or an edge, can be controlled by assigning a certain probability to the options.
If fluffy graphs are preferred, then the insertion of a new vertex should have higher probability than inserting one of the candidate edges.

Answer 6

carrying on the idea of merging two quadrangles of a quadrangulation and then reinserting a randomly chosen diagonal of the hexagon, I had the following idea, that is aimed at easy implementation:

create a planar graph that, up to a few exceptions, consists only of hexagons, e.g.

• a honeycomb mesh in the plane
• a honeycomb mesh on a cylinder

leave the sides of the hexagons unaltered, but for each hexagon, choose one of the diagonals at random, or leave it empty.

Especially the case of the honeycomb in the plane is very easy to implement: the honeycomb can be squeezed to resemble a brickwall pattern of which the presence or absence of vertical edges can be decided via the parity of the row index of the 'higher' of its adjacent vertices.
Whether a diagonal of a hexagon is present and, its orientation in case of presence, can be encoded by two bits.

Honeycombs on cylinders come in two basic variants: either spiraling or not.

Fullerene graphs http://commons.wikimedia.org/wiki/Fullerene_graphs would be an example of planar graphs, that are bipartite with the exception of twelve pentagons and would thus require some preprocessing to make them bipartite.