Are there any established methods for generating random graphs/networks that are both planar and meshlike?

Question

There are well-defined methods for generating random graphs / networks that satisfy certain properties, including small-world graphs, scale-free networks, and totally random non-planar graphs. I am looking for methods to generate random graphs that (1) are planar, and (2) have the quality that they are arranged in a lattice-like or mesh-like pattern, such that all connections are "nearby" connections only, and local loops are ubiquitous.

I suppose one could start with an actual 2-dimensional rectangular lattice, and then start randomly moving or adding edges in ways that preserve the planarity.

Thanks in advance for any thoughts, or references to known methods!

Answer 1

You could take the Delaunay triangulation of a random set of points (or, if you want almost lattices, a perturbation of something regularly defined) and remove some edges if you want.

This won't give you a small-world graph, but no lattice-like thing would. If you want something like this, you'll have to have some fractal properties anyway (if the connections are "nearby", then you'll need a lot of connections to go far).

If you want something scale-free, you can generate a Delaunay triangulation hierarchy instead -- which is a beautiful and useful tool of computationnal geometry so you'll find lots of references. The idea is to have a Delaunay triangulation on a small number of point, and then a Delaunay triangulation inside each triangle, and again, etc.