2018/02/28 by Michael Bekos, Bekos, Michael, Emilio Di Giacomo +9
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1802.10300
arxiv created 2018/06/21 · arxiv updated 2018/06/22
A topological graph is a graph drawn in the plane. A topological graph is k-plane, k>0, if each edge is crossed at most k times. We study the problem of partitioning the edges of a k-plane graph such that each partite set forms a graph with a simpler structure. While this problem has been studied for k=1, we focus on optimal 2-plane and 3-plane graphs, which are 2-plane and 3-plane graphs with maximum density. We prove the following results. (i) It is not possible to partition the edges of a simple optimal 2-plane graph into a 1-plane graph and a forest, while (ii) an edge partition formed by a 1-plane graph and two plane forests always exists and can be computed in linear time. (iii) We describe efficient algorithms to partition the edges of a simple optimal 2-plane graph into a 1-plane graph and a plane graph with maximum vertex degree 12, or with maximum vertex degree 8 if the optimal 2-plane graph is such that its crossing-free edges form a graph with no separating triangles. (iv) We exhibit an infinite family of simple optimal 2-plane graphs such that in any edge partition composed of a 1-plane graph and a plane graph, the plane graph has maximum vertex degree at least 6 and the 1-plane graph has maximum vertex degree at least 12. (v) We show that every optimal 3-plane graph whose crossing-free edges form a biconnected graph can be decomposed, in linear time, into a 2-plane graph and two plane forests.