Are there any established methods for generating random graphs/networks that are both planar and meshlike? 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 &quot;nearby&quot; 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!
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 &quot;nearby&quot;, 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.