Back to Search
Start Over
Edge partitions of optimal 2-plane and 3-plane graphs.
- Source :
-
Discrete Mathematics . Apr2019, Vol. 342 Issue 4, p1038-1047. 10p. - Publication Year :
- 2019
-
Abstract
- Abstract 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 on optimal 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 (i.e., with neither self-loops nor parallel edges) 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) There exist 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 at most 12, or with maximum vertex degree at most 8 if the optimal2-plane graph is such that its crossing-free edges form a graph with no separating triangles. (iv) There exists 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) 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 342
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 134733783
- Full Text :
- https://doi.org/10.1016/j.disc.2018.12.002