New answers tagged

0

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 ...


1

Work In progress. Feel free to contribute filling up the arguments that are incomplete. Definitions: Before proving anything we need to make it precise what is it what we are trying to prove. Planar graph: A graph that can be embedded in $\mathbb{R}^2$.(1) Plane graph: A planar graph together with a particular embedding $G\hookrightarrow\mathbb{R}^2$. I ...


0

You can probably locate a copy of Bondy and Murty's book Graph Theory with its Applications. While they don't prove it either, they give the following intuition: Let $G$ be a (connected) plane graph and $G^*$ its dual. There is a natural embedding of $G^*$ in the plane that corresponds to $G$, namely that each vertex $f^*$ in $G^*$ is placed in the ...


Top 50 recent answers are included