I was reading about line graph:

The line graph $L(G)$ of a simple graph $G$ is defined as follows: There is exactly one vertex $v(e)$ in $L(G)$ for each edge $e$ in G. For any two edges $e$ and $e'$ in $G$, $L(G)$ has an edge between $v(e)$ and $v(e')$, if and only if $e$ and $e'$ are incident with the same vertex in $G$.

Then I came across statement saying:

The line graph of a planar graph is not necessarily planar.

I see this is the case by considering e.g., the star graph $S_5$. However, can we generalize the property of the graph whose line graph results in non-planar graph. Obviously this must be the subgraphs whose line graph translates to either of Kuratowaski's graph $K_5$ or $K_{3,3}$. As pointed out, $L(K_5)=S_6$ which is planar. But $L(K_{3,3})$ is not planar (or can it be drawn as planar too?) as shown in figure below:

enter image description here

So is it like if the planar graph has a subgraph isomorphic to $S_5$, then its line graph is non planar (as it will contain $K_5$). Or is there anything more to this?

  • 1
    $\begingroup$ I didn't think $L(K_5)$ was planar? Consider that each vertex in $L(K_5)$ has degree 6, since each vertex in $K_5$ has degree 4, and would mean each edge in $K_5$ is incident to 6 other edges. Thus, $L(K_5)$ has 10 vertices and 30 edges. It can be deduced it's not planar because of it violating $e \leq 3v - 6$ ($30\not\leq 24$) $\endgroup$ – Joshua Detwiler Mar 23 '18 at 7:57

Sedlacek has shown that a graph $G$ has a planar line graph if and only if $G$ is planar of maximum degree 4 and every vertex of degree 4 is a cut vertex. Using the result, Greenwell and Hemminger [2] proved a graph $G$ has a planar line graph if and only if $G$ has no subgraph homeomorphic to $K_{3,3}$, $K_{1,5}$, $P_4+K_1$, or $K_2+\bar{K}_3$.

[1] Sedlacek, J. "Some properties of interchange graphs." Theory of Graphs and its Application (1964): 145-150.

[2] Greenwell, D. L., and Robert L. Hemminger. "Forbidden subgraphs for graphs with planar line graphs." Discrete Mathematics 2.1 (1972): 31-34.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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