# Planar graph constructed from the edges of another planar graph

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

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.

-
$H$ is not planar in all cases, e.g any graph $G$ with $\Delta >= 5$, $H$ won't be planar, are you sure you get definition correctly? would you show your reference? – Saeed Jan 24 '12 at 18:13
@Saeed It is true that $H$ is not planar in all cases. However not every graph with $\Delta \geq 5$ is a counterexample. Let $G$ be a wheel with an arbitrary number of spokes. Then $H$ will be planar. – Oliver Jan 25 '12 at 2:22
@Oliver, $H$ for wheel with an arbitrary number of spokes, is not planar. Assume you have star with $n\ge 5$ leaf, then $H$ is $K_n$ graph, and for $n\ge 5$, $H$ wont be a planar, Also your wheel contains such a star as subgraph, so $H$ for wheel contains $K_n$ as subgraph, so it's not planar. – Saeed Jan 25 '12 at 17:21
@Saeed, no the graph is planar. "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$. With the star, all the leaves are on the same face, but with the wheel each face is a triangle (well not the infinite face), so $H$ will have no cliques of size $\geq 3$. – Oliver Jan 26 '12 at 16:53
@Oliver you are right I missed the part "same face of $G$". – Saeed Jan 26 '12 at 21:47

Let $G$ be a triangle with two pendant edges attached to the same vertex. There are two distinct plane embeddings of $G$: either we put both pendant edges inside the triangle, or we put one inside and one outside. When we construct $H$ for the first embedding, we find it contains an induced $K_4$, but when we construct $H$ for the second embedding, we find that it does not.
Further $H$ won't always be planar. For example consider the previous example with more than 2 pendant edges inside the triangle.