3
$\begingroup$

This appears that a similar version of my question has been discussed on stack. Nevertheless, I have yet to see a rigorous proof.

So I presented it again.

Claim: If $G$ is a planar graph with maximum degree $\Delta(G)≤3$. Then the line graph $L(G)$ is planar.

This claim stems from the paper:

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

The original paper assumes, without proof, that the claim is correct.

This claim feels intuitively right. But how to rigorously state the proof? My feeling is that the inductive method can be used. I also tried to use the famous Kuratowski's and Wagner's theorems on the $L(G)$. But I've never been able to say it rigorously.

Fig 1

Fig1: The local structure of a vertex $v$ of degree 3.


I used $G:=K_4$ as an example to show the poof process from the answer of Brandon du Preez.

enter image description here

$\endgroup$
2
  • 2
    $\begingroup$ The question you linked and it's comment gives a good outline for a proof: use Fary's Theorem to get a straight-line embedding of $G$ in the plane, and construct $L(G)$ "on top" of it. It may even be easier to construct a planar graph that just has $L(G)$ as a minor! If you can't get this idea to work, I'm happy to write something out in full later this weekend. $\endgroup$ Aug 5 at 12:19
  • $\begingroup$ @BrandonduPreez Thank you very much for your reply. I do not yet have a good understanding of how to apply the Fray‘s Theorem. I'm still confused. It would be great to write it down in detail. Another question is how can we prove it without using such a strong theorem. It is just for fun and not to spite you. Thanks again! $\endgroup$
    – licheng
    Aug 5 at 15:13

1 Answer 1

1
$\begingroup$

We'll begin by taking $G=(V,E)$ to be any sub-cubic planar graph (i.e., $\Delta(G)\leq 3$), and embed it into the plane. Call the image of this embedding $\Gamma$ (so $\Gamma$ is a collection of points and curves in the plane).

(Step 1) We're going to modify the embedding $\Gamma$ to create a `nicer' plane graph, one where the edges are all straight lines near to any vertex. This first step can be skipped if you're happy to just apply Fary's Theorem and get a straight-line embedding of $G$.

Let $\delta = \min\{||x-y||: \text{$x$ is a vertex of $\Gamma$, $y$ is on an edge not incident with $x$}\}$. In other words, $\delta$ is the minimum distance between any vertex, and a point on an edge that doesn't touch that vertex.

Around each vertex $v$ of $\Gamma$, draw a circle $S$ of radius $\frac{\delta}{2}$ centered at $v$. We're going to modify all the edges incident with $v$ as follows: If $uv$ is an edge starting at $u$ going to $v$, consider the first point $p$ on $uv$ that touches $S$. Delete the whole segment of the edge that goes from $p$ to $uv$, and replace it with a straight line segment $[p,v]$. Do this for every edge incident with $v$, and every vertex $v$. Call the new plane graph $\Gamma'$, and note that it too is an embedding of $G$ (so it's the same graph, just drawn differently).

enter image description here

(Step 2) We're going to create a plane graph $\Gamma^*$ that has the line graph $L(G)$ as a minor - since every minor of a planar graph is planar, this will show that $L(G)$ is planar.

To create $\Gamma^*$ from $\Gamma'$, first put a vertex $\overline{e}$ in the middle of each edge $e$. Then, place a circle of radius $\frac{\delta}{4}$ around each vertex $u$ of $\Gamma'$. If the circle intersects the edge $e$ of $\Gamma'$ near to $u$, make this intersection point a new vertex called $u_e$. The arcs of the circle are now edges of a plane graph $\Gamma^*$ containing $\Gamma'$ as a subdivision.

enter image description here

To see that the line graph of $G$ is a minor of $\Gamma^*$, do the following: Remove every vertex $u$ of the original plane graph $\Gamma'$, and all the mini-edges $\{u,u_e\}$ incident with one of the original vertices. Then, contract every edge of the form $\{\overline{e}, u_e\}$. Finally, throw out any loops or duplicate edges you might have from the circles around vertices of degree 1 or 2. What's left is a plane embedding of $L(G)$.

$\endgroup$
4
  • 1
    $\begingroup$ I think it's exciting. $\endgroup$
    – licheng
    Aug 5 at 21:30
  • 1
    $\begingroup$ I'm sorry, but where did you use the condition that $\Delta(G) \leq 3$? $\endgroup$
    – koifish
    Aug 6 at 1:49
  • $\begingroup$ @koifish My feeling is that if a vertex is of degree $4$, then this method fails. In that case, it seems that something is wrong in the similar construction of $Γ^∗$ . (Note: my post refers to the paper that gives a characterizationof the planarity of line graphs, see also math.stackexchange.com/questions/1588035/…). Of course I hope Brandon du Preez gives his better explanation for your confusion. $\endgroup$
    – licheng
    Aug 6 at 4:36
  • 2
    $\begingroup$ @koifish The assumption $\Delta \leq 3$ is being used implicitly when we draw the small circles of radius $\frac{\delta}{4}$ around each vertex. When $\Delta\leq 3$, every edge is "adjacent" on this circle, so we get all the edges the line graph should have from circle arcs. But, if the degree is greater than $3$, this circle will be missing the edges of the line graph that don't have consecutive intersections with the little circle. $\endgroup$ Aug 6 at 8:30

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.