Generate planar graph in C#

Question

I am looking for a way to generate a random planar graph in C#. I've looked into some algorithms like Voronoi Diagram, Delaunay Triangulation and convex hull algorithms. They were quit useful and I managed to generate a graph but I am facing some edge cases that I didn't solve yet. Put in mind that I have 2 main constraints: min/max edge length and min/max angle(between any 2 edges), it is okay to have error in target vertex/edge count.

I think there are 2 ways to generate that graph: A. There are sources that has all possible planar graphs, I need small one so this works for me, but I don't know how to plot it on a plan without intersections. B. Generating it geometry-wise, this is what I understand the most.

I found some papers aimed for very fast generation for big graphs so it is complicated for me. I am okay with a tested slow algorithm/library/code.

Answer 1

You can create a random maximal planar graph by:

1. Start with a triangle composed of three vertices and three edges which bounds a single inner face.
2. Put that inner face into a list.
3. Pick a random inner face from the list then:

• Create a vertex in the centre of the face;
• Create edges connecting that new vertex to the three vertices around the face an trisect that original face into three new faces.
• Replace the original trisected face in the list with one of the new faces and append the other two faces to the list.

4. Repeat from 3. until you have generated a graph with sufficient vertices.

If you do not want a maximal planar graph and just want a random graph then remove edges from the graph.

• If you want a random graph then remove any edge.
• If you want a random connected graph then remove any edge that does not disconnect the graph (you can use a depth- or breadth-first search to check for connectivity).
• If you want a random biconnected graph then remove any edge that does not leave an articulation point (again, you can use a depth- or breadth-first search to check for biconnectivity)

Put in mind that I have 2 main constraints: min/max edge length and min/max angle(between any 2 edges)

This is an issue with the embedding the graph onto a surface and not necessarily with the structure of the graph as you can move a vertex and change the angles and edge lengths. You can try using any planar graph drawing algorithm to generate an embedding and then use something like a spring-embedding algorithm to try to modify the embedding to match your constraints.