arXiv Open Access 2024

On $k$-Plane Insertion into Plane Drawings

Julia Katheder Philipp Kindermann Fabian Klute Irene Parada Ignaz Rutter

Lihat Sumber

Abstrak

We introduce the $k$-Plane Insertion into Plane drawing ($k$-PIP) problem: given a plane drawing of a planar graph $G$ and a set $F$ of edges, insert the edges in $F$ into the drawing such that the resulting drawing is $k$-plane. In this paper, we show that the problem is NP-complete for every $k\ge 1$, even when $G$ is biconnected and the set $F$ of edges forms a matching or a path. On the positive side, we present a linear-time algorithm for the case that $k=1$ and $G$ is a triangulation.

Topik & Kata Kunci

cs.CG

Penulis (5)

Julia Katheder

Philipp Kindermann

Fabian Klute

Irene Parada

Ignaz Rutter

Format Sitasi

APA MLA BibTeX

Katheder, J., Kindermann, P., Klute, F., Parada, I., Rutter, I. (2024). On $k$-Plane Insertion into Plane Drawings. https://arxiv.org/abs/2402.14552

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2024
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓