2026/07/28 by Miriam Goetze, Michael Kaufmann, Soeren Terziadis
#math.CO
In this work, we introduce t-colorable k-plane drawings, that is, drawings of graphs with a t-edge-coloring where every edge is crossed by at most k edges of each color. We give tight upper bounds on the edge- and crossing density for small values of t and k and show that the recognition of such drawings is NP-complete if t≥ 2 and k≥1.