Miscellaneous properties of embeddings of line, total and middle graphs

Abstract

Chartrand et al. (J. Combin. Theory Ser. B 10 (1971) 12–41) proved that the line graph of a graph G is outerplanar if and only if the total graph of G is planar. In this paper, we prove that these two conditions are equivalent to the middle graph of G been generalized outerplanar. Also, we show that a total graph is generalized outerplanar if and only if it is outerplanar. Later on, we characterize the graphs G such that Full-size image (<1 K) is planar, where Full-size image (<1 K) is a composition of the operations line, middle and total graphs. Also, we give an algorithm which decides whether or not Full-size image (<1 K) is planar in an Full-size image (<1 K) time, where n is the number of vertices of G. Finally, we give two characterizations of graphs so that their total and middle graphs admit an embedding in the projective plane. The first characterization shows the properties that a graph must verify in order to have a projective total and middle graph. The second one is in terms of forbidden subgraphs.