Generate a large random planar graph

Question

What is the most efficient way to generate a large (~ 300k vertices) random planar graph ("random" here means uniformly distributed)?

Lulalulea

What does "uniformly distributed" mean? Do you mean selected from the set of N planar graphs having M nodes with uniform probability 1/N? Do you have an idea of how astronomically huge N is for even a dozen nodes? – Jepum

Answer 1

Have you looked at Boltzmann sampling? See the paper by Eric Fusy "Uniform random sampling of planar graphs in linear time". The paper and the implementation are available in his homepage which the paper says can generate instances of size 100K in a few seconds.

Ardene

This is the correct answer for uniform distribution. – Burdick

@Ardene the page had been shifted. And new page does not have the source code. – Selaginella

Available still via waybackmachine: web.archive.org/web/20200521230940/http://… – Wimer

Answer 2

Another possibility consists in randomly choosing coordinates and then compute a Delaunay Triangulation, which is a planar graph (and looks nice as well). See http://en.wikipedia.org/wiki/Delaunay_triangulation There are O(n log(n)) algorithms to compute such a triangulation.

Hargeisa

but it will have fixed degree 3? – Ephebe

It will not have fixed degree 3, but it will be planar. – Beefcake

This answer is wrong. This will not give uniform distribution, as required in the question. – Burdick

This produces only graphs with chordless cycles of length 3 (ie, triangular loops), which may not always be desirable. – Madalynmadam

Answer 3

Without any other requirements, I'd say look up random maze generation. If you want cycles in the graph, remove some walls at random from a simple maze. The intersections in the maze become the nodes in your graph and the removed walls are the edges. That means you can select the number of nodes by choosing the size of the maze.

Mazes are typically done on a 2d grid with at most 4 connections from one point to another, but there is nothing stopping you from doing a maze on hex tiles, or something else.

Topfull

Answer 4

If by uniform you mean uniformly distributed in space, then this is a pretty fast algorithm I developed for generating planar graphs for a spatial ecological/evolutionary simulator. It will generate random planar graphs with an expected degree you specify, of course with some variation around it. You could extend it to pick the expected degree based on a uniform random number if instead you wanted uniform random degrees in your planar graph.

https://github.com/briandconnelly/seeds/blob/master/seeds/plugins/topology/CartesianTopology.py

Interlineate

It seems this algorithm can generate graphs whose edges cross ? That is not a planar graph. For example, if there are 4 points in a circle of the given radius, they will all connect to each other and the diagonals will cross, making the graph non-planar. – Accent

Answer 5

Well one method would be to try and generate a random graph which satisfies similar constraints as a planar graph (for instance, edges <= 3*vertices - 6) and check if it is planar in O(n) time using Tarjan's planarity testing algorithm. If it is not planar, generate again. Not sure how efficient this would be for 300K vertices!, though (or if it will even give you graphs with uniform probability).

There is some literature on generating planar graphs, I could find one paper here : Generating Labeled Planar Graphs which apparently has expected O(n^4) running time, and might not be worth it either. Perhaps the references there will help you track down something that might help.

Good luck!

Bucephalus

surely almost all random graphs are not planar? – Ephebe

Random graphs are planar with only exponentially small probability, meaning the suggested algorithm has exponential time complexity! Alas, random graphs have a completely different structure than planar graphs (e.g. spectral properties). – Burdick

Answer 6

I don`t know, what you mean by 'uniformly distributed'?

I use the following code (PHP), to generate a randomized maximum planar graph. You have to delete some connection, if you don't want to get an not maximum planar graph. (I don't think, that the algorithm is efficient. The calculation of the edges is perhaps not needed. The use of the storage-management and indexing could definitively done better [array_keys, shuffle, ...]. But it worked for me with smaller cases.)

    class MapGenerator
    {
        protected const MINIMUM_CONST = 3;
    
       protected const MINIMUM_MAP = [
            1 => [
                self::KEY_CONNECT => [2, 3], // connect to every node in the triangle
            ],
            2 => [
                self::KEY_CONNECT => [3, 1],
            ],
            3 => [
                self::KEY_CONNECT => [1, 2],
            ],
        ];
        protected const KEY_MINIMUM_MAP = '1-2-3';
        const KEY_CONNECT = 'connect';
    
        public function generatePlanarMap($nodeCounts = 10)
        {
            $this->map = self::MINIMUM_MAP;
            $this->areas = [self::KEY_MINIMUM_MAP => []];
            if ($nodeCounts > self::MINIMUM_CONST) {
                /** @var int $newNode */
                for ($newNode = self::MINIMUM_CONST + 1; $newNode <= $nodeCounts; $newNode++) {
                    $myKeys = array_keys($this->areas);
                    shuffle($myKeys);
                    $randomArea = $myKeys[0];
    // remove the selected area, which will be splitted up to three new areas by including the new node
                    unset($this->areas[$randomArea]);
    
                    $listTriangleNodes = $this->decodeAreaToKeys($randomArea);
                    $this->map[] = [
                        self::KEY_CONNECT => $listTriangleNodes,
                    ];
                    $newNodeKey = count($this->map);
                    $this->map[$listTriangleNodes[0]][self::KEY_CONNECT][] = $newNodeKey;
                    $this->map[$listTriangleNodes[1]][self::KEY_CONNECT][] = $newNodeKey;
                    $this->map[$listTriangleNodes[2]][self::KEY_CONNECT][] = $newNodeKey;
    
    // detect the three new triagulations, which are generated by the new node
                    foreach ([[0, 1], [1, 2], [0, 2]] as $variation) {
// I have not tested this part 
                        $this->areas[$this->defineKeyForArea($newNodeKey, $listTriangleNodes[$variation[0]], $listTriangleNodes[$variation[1]])] = [
                            self::KEY_CONNECT => [
                                ($newNodeKey < $listTriangleNodes[$variation[0]] ? [$newNodeKey, $listTriangleNodes[$variation[0]],] : [$listTriangleNodes[$variation[0]], $newNodeKey,]),
                                ($newNodeKey < $listTriangleNodes[$variation[1]] ? [$newNodeKey, $listTriangleNodes[$variation[1]],] : [$listTriangleNodes[$variation[1]], $newNodeKey,]),
                                ($listTriangleNodes[$variation[0]] < $listTriangleNodes[$variation[1]] ? [$listTriangleNodes[$variation[0]], $listTriangleNodes[$variation[1]],] : [$listTriangleNodes[$variation[1]], $listTriangleNodes[$variation[0]],]),
                            ],
                        ];
                    }
                }
            }
            $this->areas[self::KEY_MINIMUM_MAP] = [
                self::KEY_CONNECT => [[1, 2], [1, 3], [2, 3],],
            ];
        }
    
        protected function decodeAreaToKeys(string $area)
        {
            return explode('-', $area);
        }
    
    }

Remark: Every generated graph fullfill the 4-color-theorem, because the color of each node can defined through the generation of the map. I tried to find an algorithm, which can colorize the graph by starting at a random node and not knowing the generation. I was not successful until now.

Hives