My recipy 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.

An even simpler and faster way would be to remove from a planar grid graph randomly selected vertices and/or edges; that could be realized in software by changing the value of Boolean flags that are associated with the vertices and edges.

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.

My recipy 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 Delauny 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.

My recipy 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.

An even simpler and faster way would be to remove from a planar grid graph randomly selected vertices and/or edges; that could be realized in software by changing the value of Boolean flags that are associated with the vertices and edges.