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