On Partitioning the Edges of 1-Plane Graphs

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.

In collections

File details
ID Label Size Mimetype Created
OBJ OBJ datastream 352.39 KiB application/pdf 2020-06-15
TN TN 2.04 KiB image/jpeg 2020-06-15