2020/12/03 by Fabian Klute, Irene Parada, Klute, Fabian +1
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2012.02281
openalex publication_date 2020/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A drawing of a graph is k-plane if no edge is crossed more than k times. In this paper we study saturated k-plane drawings with few edges. This are k-plane drawings in which no edge can be added without violating k-planarity. For every number of vertices n>k+1, we present a tight construction with (n-1)/(k+1) edges for the case in which the edges can self-intersect. If we restrict the drawings to be ℓ-simple we show that the number of edges in saturated k-plane drawings must be higher. We present constructions with few edges for different values of k and ℓ. Finally, we investigate saturated straight-line k-plane drawings.