0
$\begingroup$

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.

  • 0
    @Oliver you are right I missed the part "same face of $G$".2012-01-26

1 Answers 1

1

I don't know a name for this construction. I suspect that there isn't a standard name, as the construction does in fact depend on the plane embedding.

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.

The more general construction is that of line graphs, which require no planarity hypothesis and have lots of nice properties.

  • 1
    Thank you for your answer. The construction I described in my question seems to be called the "medial graph", according to the Wikipedia article you linked.2012-01-26