Let $G$ be a planar graph. We construct a graph $H$ from $G$ in the following manner :
- The vertices of $H$ are interior points of the edges of $G$, one on each edge.
- Two vertices of $H$ are joined by an edge if and only if the two edges of $G$ corresponding to them have a common vertex in $G$ and are incident to the same face of $G$.
It's easy to see that $H$ is planar.
So for instance, if $G$ is the complete graph on 4 vertices, then $H$ will be a hexagram ("star of david") whose six vertices are joined in a cycle (I hope you get the picture).
Does this construction have a name ? I have some difficulty finding more information about this without a name.
And is $H$ independent of the plane embedding of $G$ used ? I think yes, but I'm not sure.
Context : this construction is used in a proof of Steinitz's theorem.