arxiv: 2605.14834 · v1 · submitted 2026-05-14 · 💻 cs.CG · cs.DS

Recognition: no theorem link

Min-1-Planarity is NP-Hard

Yuto Okada

Authors on Pith no claims yet

Pith reviewed 2026-05-15 03:13 UTC · model grok-4.3

classification 💻 cs.CG cs.DS

keywords min-1-planarityNP-hardnessgraph drawingplanarity testingNP-completenesscomputational complexity

0 comments

The pith

Deciding whether a graph admits a min-1-planar drawing is NP-hard.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that there is no efficient algorithm to test whether an arbitrary graph can be drawn in the plane such that every crossing involves at least one edge crossed at most once overall. This min-1-planar condition relaxes ordinary planarity while still constraining how crossings may occur. A sympathetic reader cares because the result shows that even this limited relaxation of planarity remains intractable, directly affecting the feasibility of automated graph layout tools. The proof proceeds via a polynomial-time reduction from a known NP-complete problem that preserves the yes/no answer exactly.

Core claim

The central claim is that min-1-planarity testing is NP-hard. A drawing is min-1-planar when, for every crossing, at least one of the two edges is crossed at most once in the whole drawing. The authors establish this hardness by constructing a polynomial-time reduction from an established NP-complete problem to the recognition question for min-1-planar drawings.

What carries the argument

A polynomial-time reduction from a known NP-complete problem to min-1-planarity testing that maps yes-instances to graphs admitting min-1-planar drawings and no-instances to graphs that do not.

If this is right

No polynomial-time algorithm exists for min-1-planarity testing unless P equals NP.
Exact or heuristic methods are required for practical computation of min-1-planar drawings.
Related crossing-constrained drawing problems inherit similar intractability.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Hardness may extend to min-k-planarity for other small fixed k values.
Fixed-parameter tractable algorithms could be sought when the number of crossings or graph treewidth is bounded.
Approximation algorithms for minimum crossings under the min-1 constraint become relevant for visualization applications.

Load-bearing premise

The constructed reduction correctly preserves the yes and no answers of the source NP-complete problem.

What would settle it

A polynomial-time algorithm that decides min-1-planarity for every input graph, or a specific graph produced by the reduction whose min-1-planarity status contradicts the source instance.

read the original 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\"{u}ngener, Di Battista, Didimo, Dujmovi\'c, Hong, Kaufmann, Liotta, Morin, and Tappini [GD 2023; JGAA, 2024] as a generalization of $k$-planarity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper shows min-1-planarity testing is NP-hard via a standard reduction, a useful but narrow follow-up to the 2023 definition.

read the letter

The core result is that deciding whether a graph has a min-1-planar drawing is NP-hard. This pins down the complexity for the min-k-planarity notion right at k=1, which is new since the definition itself only appeared last year. The abstract frames it cleanly as a generalization of k-planarity where each crossing must involve an edge with at most one crossing total. That distinction matters for drawing algorithms that want to bound local crossing density without forcing global planarity. The work follows the expected route: a polynomial-time reduction from a known NP-complete problem, with gadgets that enforce the min-1 condition while preserving yes/no instances. If the gadgets are constructed to avoid extra crossings that would violate the bound, the argument should hold. The paper does well at stating the problem and citing the prior definition paper without overclaiming broader impact. The reduction strategy itself is conventional for this area, which is fine as long as the details check out. The main soft spot is that the abstract gives no gadget diagrams or correctness lemmas, so any subtle flaw in how crossings are counted or how the min-1 property is maintained across the whole drawing would only surface in the full proof. No circularity or invented entities appear in the given material. This is the sort of targeted complexity result that computational geometry and graph drawing groups track. A reader already working on crossing variants or planarity testing will get direct value from the classification. It is not foundational enough to cite outside that niche, but the claim is sharp enough that a serious editor should send it to referees rather than desk-reject. The evidence presented supports treating it as a legitimate hardness proof once the reduction is verified.

Referee Report

0 major / 2 minor

Summary. The paper proves that deciding whether an arbitrary graph admits a min-1-planar drawing is NP-hard. A drawing is defined to be min-1-planar when every crossing involves at least one edge that participates in at most one crossing overall; the authors establish the result via a polynomial-time reduction from a known NP-complete problem (presumably a planar variant of 3-SAT or 3-coloring) that constructs a graph whose min-1-planar drawings exist if and only if the source instance is satisfiable.

Significance. If the reduction is correct, the result places a natural and recently introduced relaxation of k-planarity into the NP-hard regime, complementing existing polynomial-time results for stricter planarity variants and informing the design of exact algorithms or approximation schemes for graph drawing. The work supplies a concrete complexity boundary that can guide future research on crossing-minimization problems.

minor comments (2)

§2, Definition 1: the phrasing 'involves at most k crossings' could be reworded to 'is incident to at most k crossings' to avoid any ambiguity about whether the count includes the current crossing.
Figure 3: the gadget diagram would benefit from an explicit legend distinguishing the 'crossing edges' from the 'frame edges' used in the reduction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary and recommendation to accept the paper. We are pleased that the work is viewed as providing a useful complexity boundary for min-k-planarity.

Circularity Check

0 steps flagged

No significant circularity in the NP-hardness reduction

full rationale

The paper proves NP-hardness of deciding min-1-planarity via a standard polynomial-time reduction from an independently established NP-complete problem. The definition of min-1-planarity is taken from prior work by unrelated authors (Binucci et al., GD 2023 / JGAA 2024) and is not redefined in terms of the hardness result itself. No equations, parameters, or uniqueness claims reduce to self-citations or fitted inputs by construction; the derivation chain consists of an external reduction that preserves yes/no instances without circular dependence on the target property.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on a standard polynomial-time many-one reduction from an NP-complete problem; no free parameters, invented entities, or non-standard axioms are visible in the abstract.

axioms (1)

standard math NP-completeness of the source problem and correctness of the reduction gadgets
The proof technique relies on the established theory of NP-hardness reductions.

pith-pipeline@v0.9.0 · 5396 in / 1011 out tokens · 48977 ms · 2026-05-15T03:13:31.806385+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

2-level quasi-planarity or how caterpillars climb (spqr-)trees

2 Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, and Maurizio Patrignani. 2-level quasi-planarity or how caterpillars climb (spqr-)trees. In Dániel Marx, editor,Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2779–2798. SIAM,

work page 2021
[2]

In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp

doi:10.1137/1. 9781611976465.165. 3 Michael A. Bekos, Sabine Cornelsen, Luca Grilli, Seok-Hee Hong, and Michael Kaufmann. On the recognition of fan-planar and maximal outer-fan-planar graphs. In Christian A. Duncan and Antonios Symvonis, editors,Graph Drawing - 22nd International Symposium, GD 2014, Würzburg, Germany, September 24-26, 2014, Revised Select...

work page doi:10.1137/1 2014
[3]

5 Carla Binucci, Aaron Büngener, Giuseppe Di Battista, Walter Didimo, Vida Dujmović, Seok- Hee Hong, Michael Kaufmann, Giuseppe Liotta, Pat Morin, and Alessandra Tappini

URL:https://doi.org/10.1007/s00453-016-0200-5, doi: 10.1007/S00453-016-0200-5. 5 Carla Binucci, Aaron Büngener, Giuseppe Di Battista, Walter Didimo, Vida Dujmović, Seok- Hee Hong, Michael Kaufmann, Giuseppe Liotta, Pat Morin, and Alessandra Tappini. Min-k- planar drawings of graphs. In Michael A. Bekos and Markus Chimani, editors,Graph Drawing and Network...

work page doi:10.1007/s00453-016-0200-5 2023
[4]

7 Carla Binucci, Emilio Di Giacomo, Walter Didimo, Fabrizio Montecchiani, Maurizio Patrignani, Antonios Symvonis, and Ioannis G

URL:https: //doi.org/10.7155/jgaa.v28i2.2925,doi:10.7155/JGAA.V28I2.2925. 7 Carla Binucci, Emilio Di Giacomo, Walter Didimo, Fabrizio Montecchiani, Maurizio Patrignani, Antonios Symvonis, and Ioannis G. Tollis. Fan-planarity: Properties and complexity.Theor. Comput. Sci., 589:76–86,

work page doi:10.7155/jgaa.v28i2.2925
[5]

8 Franz J

URL:https://doi.org/10.1016/j.tcs.2015.04.020, doi: 10.1016/J.TCS.2015.04.020. 8 Franz J. Brandenburg. Recognizing optimal 1-planar graphs in linear time.Algorith- mica, 80(1):1–28,

work page doi:10.1016/j.tcs.2015.04.020 2015
[6]

9 Zhi-Zhong Chen, Michelangelo Grigni, and Christos H

URL:https://doi.org/10.1007/s00453-016-0226-8, doi:10.1007/ S00453-016-0226-8. 9 Zhi-Zhong Chen, Michelangelo Grigni, and Christos H. Papadimitriou. Recognizing hole-free 4-map graphs in cubic time.Algorithmica, 45(2):227–262,

work page doi:10.1007/s00453-016-0226-8
[7]

1007/s00453-005-1184-8,doi:10.1007/S00453-005-1184-8

URL:https://doi.org/10. 1007/s00453-005-1184-8,doi:10.1007/S00453-005-1184-8. 10 Reinhard Diestel.Graph Theory, volume 173 ofGraduate Texts in Mathematics. Springer Berlin, 6th edition, 2025.doi:10.1007/978-3-662-70107-2. 11 Emeric Gioan. Complete graph drawings up to triangle mutations.Discret. Comput. Geom., 67(4):985–1022,

work page doi:10.1007/s00453-005-1184-8 2025
[8]

12 Alexander Grigoriev and Hans L

URL:https://doi.org/10.1007/s00454-021-00339-8, doi:10.1007/ S00454-021-00339-8. 12 Alexander Grigoriev and Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge.Algorithmica, 49(1):1–11,

work page doi:10.1007/s00454-021-00339-8
[9]

13 Petr Hliněný and Csenge Lili Ködmön

URL:https://doi.org/10.1007/ s00453-007-0010-x,doi:10.1007/S00453-007-0010-X. 13 Petr Hliněný and Csenge Lili Ködmön. Note on min-k-planar drawings of graphs. In Stefan Felsner and Karsten Klein, editors,32nd International Symposium on Graph Drawing and Network Visualization, GD 2024, Vienna, Austria, September 18-20, 2024, LIPIcs, pages 8:1–8:10. Schloss...

work page doi:10.1007/s00453-007-0010-x 2024
[10]

14 Heather Hulett, Todd G

URL:https://doi.org/ 10.4230/LIPIcs.GD.2024.8,doi:10.4230/LIPICS.GD.2024.8. 14 Heather Hulett, Todd G. Will, and Gerhard J. Woeginger. Multigraph realizations of degree sequences: Maximization is easy, minimization is hard.Oper. Res. Lett., 36(5):594–596,

work page doi:10.4230/lipics.gd.2024.8 2024
[11]

15 Miriam Münch and Ignaz Rutter

URL:https://doi.org/10.1016/j.orl.2008.05.004,doi:10.1016/J.ORL.2008.05.004. 15 Miriam Münch and Ignaz Rutter. Parameterized algorithms for beyond-planar crossing numbers. In Stefan Felsner and Karsten Klein, editors,32nd International Symposium on Graph Drawing and Network Visualization, GD 2024, Vienna, Austria, September 18-20, 2024, LIPIcs, pages 25:1...

work page doi:10.1016/j.orl.2008.05.004 2008
[12]

16 Nabil H Rafla.The good drawings Dn of the complete graph Kn

URL: https://doi.org/10.4230/LIPIcs.GD.2024.25,doi:10.4230/LIPICS.GD.2024.25. 16 Nabil H Rafla.The good drawings Dn of the complete graph Kn. PhD thesis, McGill University, Montreal,

work page doi:10.4230/lipics.gd.2024.25 2024
[13]

18 David R

URL:https://doi.org/10.1016/j.ipl.2020.106083, doi:10.1016/ J.IPL.2020.106083. 18 David R. Wood and Jan Arne Telle. Planar decompositions and the crossing number of graphs with an excluded minor. In Michael Kaufmann and Dorothea Wagner, editors,Graph Drawing, 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18-20, Y. Okada 13

work page doi:10.1016/j.ipl.2020.106083 2020
[14]

19 David R

doi:10.1007/978-3-540-70904-6\_16. 19 David R. Wood and Jan Arne Telle. Planar decompositions and the crossing number of graphs with an excluded minor.New York Journal of Mathematics, 13:117–146,

work page doi:10.1007/978-3-540-70904-6
[15]

URL: https://nyjm.albany.edu/j/2007/13-8.html

work page 2007