Back to Search
Start Over
On partitioning the edges of 1-plane graphs.
- Source :
-
Theoretical Computer Science . Feb2017, Vol. 662, p59-65. 7p. - Publication Year :
- 2017
-
Abstract
- A 1-plane graph is a graph embedded in the plane such that each edge is crossed at most once. A 1-plane graph is optimal if it has maximum edge density. A red–blue edge coloring of an optimal 1-plane graph G partitions the edge set of G into blue edges and red edges such that no two blue edges cross each other and no two red edges cross each other. We prove the following: ( i ) Every optimal 1-plane graph has a red–blue edge coloring such that the blue subgraph is maximal planar while the red subgraph has vertex degree at most four; this bound on the vertex degree is worst-case optimal. ( ii ) A red–blue edge coloring may not always induce a red forest of bounded vertex degree. Applications of these results to graph augmentation and graph drawing are also discussed. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPHIC methods
*GEOMETRIC vertices
*GEOMETRICAL drawing
*ANGLES
*COLORS
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 662
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 120559735
- Full Text :
- https://doi.org/10.1016/j.tcs.2016.12.004