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
- a fullerene graph http://commons.wikimedia.org/wiki/Fullerene_graphs
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.