2026-07-26T01:00:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21319 2024-10-28T09:51:05Z ddc:004 open_access

On k-Plane Insertion into Plane Drawings Katheder, Julia Kindermann, Philipp Klute, Fabian Parada, Irene Rutter, Ignaz Graph drawing edge insertion k-planarity 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 ≥ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julia Katheder and Philipp Kindermann and Fabian Klute and Irene Parada and Ignaz Rutter 2024 Is Part Of LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2024.35 urn:nbn:de:0030-drops-213190 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.35 eng https://creativecommons.org/licenses/by/4.0/legalcode