Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
$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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
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. –  pokraka Jan 26 '12 at 16:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.