Saturated K-Plane Drawings with Few Edges

Fabian Klute, Irene Parada

Research output: Working paperPreprintAcademic


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−1k+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.
Original languageEnglish
Number of pages25
Publication statusPublished - 3 Dec 2020


Dive into the research topics of 'Saturated K-Plane Drawings with Few Edges'. Together they form a unique fingerprint.

Cite this