Search code examples
pythongraphdata-analysis

Generating a random planar graph in python

I am looking to generate a random planar graph in python with around 20 vertices. I checked out this planar graph generator but two problems emerged:

  1. The algorithm on the aforementioned GitHub project seems a bit too overkill to generate a random planar graph that doesn’t have those many edges
  2. Because it’s meant to generate massive graph, that algorithm is very complex, and therefore also a bit clunky and difficult to use

With that said, is there a simpler way to randomly generate a relatively small planar graph in python?

Solution 
  • Create required number of nodes
Assign random x,y locations to the nodes.
WHILE nodes with no connected edges
    Select N a random node with no edge
    LOOP select M a different node at random
        IF edge N-M does NOT intersect previous edges
             Add N-M edge to graph
             BREAK out of LOOP