Abstract:In this paper, we show that it is NP-hard to determine whether a given graph admits a min-1-planar drawing. A drawing of a graph is min-$k$-planar if, for every crossing in the drawing, at least one of the two crossing edges involves at most $k$ crossings. This notion of min-$k$-planarity was introduced by Binucci, Büngener, Di Battista, Didimo, Dujmović, Hong, Kaufmann, Liotta, Morin, and Tappini [GD 2023; JGAA, 2024] as a generalization of $k$-planarity.
From: Yuto Okada [view email]
[v1]
Thu, 14 May 2026 13:40:04 UTC (222 KB)
[v2]
Fri, 22 May 2026 10:01:14 UTC (223 KB)
[v3]
Thu, 2 Jul 2026 06:33:37 UTC (225 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。