Saturated K-Plane Drawings with Few Edges

Fabian Klute; Irene Parada

doi:10.48550/arXiv.2012.02281

Saturated K-Plane Drawings with Few Edges

Fabian Klute, Irene Parada

Research output: Working paper › Preprint › Academic

Abstract

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 language	English
Publisher	arXiv
Pages	1-25
Number of pages	25
DOIs	https://doi.org/10.48550/arXiv.2012.02281
Publication status	Published - 3 Dec 2020

Access to Document

10.48550/arXiv.2012.02281Licence: CC BY

2012.02281Submitted manuscript, 610 KBLicence: CC BY

Cite this

@techreport{c96926fc319542fbb1c1ce8977e1e853,

title = "Saturated K-Plane Drawings with Few Edges",

abstract = "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.",

author = "Fabian Klute and Irene Parada",

year = "2020",

month = dec,

day = "3",

doi = "10.48550/arXiv.2012.02281",

language = "English",

pages = "1--25",

publisher = "arXiv",

type = "WorkingPaper",

institution = "arXiv",

}

TY - UNPB

T1 - Saturated K-Plane Drawings with Few Edges

AU - Klute, Fabian

AU - Parada, Irene

PY - 2020/12/3

Y1 - 2020/12/3

N2 - 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.

AB - 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.

U2 - 10.48550/arXiv.2012.02281

DO - 10.48550/arXiv.2012.02281

M3 - Preprint

SP - 1

EP - 25

BT - Saturated K-Plane Drawings with Few Edges

PB - arXiv

ER -

Saturated K-Plane Drawings with Few Edges

Abstract

Access to Document

Fingerprint

Cite this