On the Planarity of Generalized Line Graphs

Abstract

One of the most familiar derived graphs is the line graph. The line graph $L(G)$ of a graph $G$ is that graph whose vertices are the edges of $G$ where two vertices of $L(G)$ are adjacent if the corresponding edges are adjacent in~$G$. Two nontrivial paths $P$ and $Q$ in a graph $G$ are said to be adjacent paths in $G$ if $P$ and $Q$ have exactly one vertex in common and this vertex is an end-vertex of both $P$ and $Q$. For an integer $\ell \ge 2$, the $\ell$-line graph $L_{\ell}(G)$ of a graph~$G$ is the graph whose vertex set is the set of all $\ell$-paths (paths of order~$\ell$) of $G$ where two vertices of $L_{\ell}(G)$ are adjacent if they are adjacent $\ell$-paths in $G$. Since the 2-line graph is the line graph $L(G)$ for every graph~$G$, this is a generalization of line graphs. In this work, we study planar and outerplanar properties of the 3-line graph of connected graphs and present characterizations of those trees having a planar or outerplanar 3-line graph by means of forbidden subtrees.

Keywords

• line graph
• l-line graph
• planar and outerplanar graphs