General planar graph $L(G)$

72 Views Asked by At

Let $G=(V,E)$ be a graph. Show that if $G$ is planar and $3$-regular then the line-graph $L(G)$ corresponding to $G$ is also planar.

Considering small examples might help. I can find an embedding for the tetrahedron, for instance. I need to find a planar embedding for $L(G)$ by manipulating the planar embedding that I can find for $G$. So let $(\mathcal{P}, \Gamma)$ be a planar embedding for $G,$ where $\Gamma$ is a set of simple curves representing edges and $\mathcal{P}$ is a set of points representing vertices. Vertices of $L(G)$ are adjacent iff they share a common vertex. We think of the edges in $\Gamma$ as vertices in $L(G).$ For any pair of edges in $\Gamma$ with a common vertex, we connect them with an edge in $L(G).$ Since the degree of every vertex of the graph is $3$, around every vertex $v$ and the edges in $\Gamma$ are continuous, we can draw $3$ edges that do not intersect and connect all $3$ pairs of edges incident with $v$. We can then delete repeated edges so that there is exactly one of each edge. I think this yields a planar embedding of $L(G),$ but I'm not really sure how to justify this more formally; perhaps it's wrong?