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
    $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?2012-01-24
  • 0
    @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.2012-01-25
  • 0
    @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.2012-01-25
  • 0
    @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$.2012-01-26
  • 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