All 2-planar graphs having the same spanning subgraph

Abstract

A graph drawn on the plane is 2-immersed in the plane if each edge is crossed by at most two other edges (this plane drawing of the graph is called a 2-immersion of the graph in the plane). A graph is 2-planar if it can be 2-immersed in the plane. We consider the class T of all finite planar graphs triangulating the plane such that the graphs have no loops and multiple edges, the vertices have degree 5 and 6 only, and the distance between any two 5-valent vertices is at least 4. We describe all possible 2-immersions that a graph of the class T can have and for any of such 2-immersions, we describe all possible ways in which new edges can be added in the 2-immersion to obtain a new 2-immersed graph.