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)?

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? — Spacedman, Jun 28 '21 at 10:37

score 8 · Answer 1 · answered May 08 '13 at 08:23

8

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.

answered May 08 '13 at 08:23

Valentas

2,014
20
24

1

This is the correct answer for uniform distribution. – user2316602 Mar 16 '19 at 19:58
@Valentas the page had been shifted. And new page does not have the source code. – Subhankar Ghosal Apr 23 '22 at 16:22
Available still via waybackmachine: http://web.archive.org/web/20200521230940/http://www.lix.polytechnique.fr/~fusy/Programs/BoltzmannPlanarGraphs.tar.gz – Dave Nolan May 28 '22 at 14:09

score 7 · Answer 2 · answered Jan 15 '13 at 10:41

7

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.

answered Jan 15 '13 at 10:41

Ivo Blöchliger

79
1
2

but it will have fixed degree 3? – andrew cooke Jan 15 '13 at 11:36
1

It will not have fixed degree 3, but it will be planar. – Ivo Blöchliger Jan 23 '13 at 18:11
3

This answer is wrong. This will not give uniform distribution, as required in the question. – user2316602 Mar 16 '19 at 19:54
1

This produces only graphs with chordless cycles of length 3 (ie, triangular loops), which may not always be desirable. – a52 Nov 13 '19 at 21:44

score 3 · Answer 3 · answered Jan 19 '11 at 16:36

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.

score 2 · Answer 4 · edited Jul 31 '17 at 14:30

2

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

edited Jul 31 '17 at 14:30

Peter O.

32,158
14
82
96

answered Apr 03 '11 at 14:52

LuisZaman

104
4

3

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. – Sid Datta Nov 29 '12 at 21:10

score 1 · Answer 5 · 2010-07-12T21:31:02.820

1

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!

edited Jul 12 '10 at 21:31

answered Jul 12 '10 at 21:25

4

surely almost all random graphs are not planar? – andrew cooke Jan 15 '13 at 11:35
1

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). – user2316602 Mar 16 '19 at 19:57

Generate a large random planar graph

5 Answers5

Linked

Related