Miscellaneous properties of embeddings of line, total and middle graphs (Q5936016)

The authors examine embeddings of the line graph, middle graph, and total graph of a given graph \(G\). They are interested in when these derived graphs are planar, outerplanar, or generalized outerplanar (where at least one endvertex of each edge is on the boundary of the outer face). NEWLINENEWLINENEWLINEResults include: (1) the line graph of \(G\) is outerplanar if and only if the total graph of \(G\) is planar if and only if the middle graph of \(G\) is generalized outerplanar (one equivalence was previously known), (2) the total graph is generalized outerplanar if and only if the total graph is outerplanar, (3) a characterization of graphs whose composition of the line, middle, and total graph operations are planar, and (4) a characterization of graphs whose total or middle graphs embed in the projective plane both in terms of their properties and in terms of forbidden subgraphs.