pith. sign in

arxiv: 2605.14834 · v2 · pith:5NODSS24new · submitted 2026-05-14 · 💻 cs.CG · cs.DS

Min-1-Planarity is NP-Hard

Yuto Okada This is my paper

Pith reviewed 2026-05-25 06:41 UTC · model grok-4.3

classification 💻 cs.CG cs.DS
keywords min-1-planarityNP-hardnessgraph drawingcrossing numbercomputational complexityplanarity testing
0
0 comments X

The pith

Deciding whether a graph has 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 recognizing whether an arbitrary graph can be drawn so every crossing touches an edge crossed at most once overall is NP-hard. Min-1-planarity relaxes standard planarity by permitting crossings provided one of the two edges stays lightly crossed. The result follows from a polynomial-time reduction that maps instances of a known NP-hard problem onto graphs whose min-1-planar status encodes the original answer. A reader cares because the hardness persists even under this relaxed crossing rule, closing off efficient recognition for this class.

Core claim

It is NP-hard to determine whether a given graph admits a min-1-planar drawing, where a drawing is min-1-planar if every crossing involves at least one edge that participates in at most one crossing total.

What carries the argument

A polynomial-time reduction from a known NP-hard problem that produces graphs whose min-1-planarity encodes the source instance.

If this is right

  • No efficient algorithm exists for min-1-planarity unless P equals NP.
  • Recognition remains hard even when crossings are allowed on edges that cross only once.
  • The same reduction technique may extend to show hardness for min-k-planarity at small fixed k.

Where Pith is reading between the lines

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

  • Min-k-planarity may stay NP-hard for every constant k, not just k=1.
  • Practical drawing heuristics for this model would need to handle exponential search in the worst case.
  • The result separates min-1-planarity from 1-planarity, whose complexity status remains open.

Load-bearing premise

The constructed reduction correctly preserves yes/no answers and runs in polynomial time.

What would settle it

Discovery of a polynomial-time algorithm that correctly decides min-1-planarity for all graphs, or an explicit counterexample showing the reduction maps a yes-instance to a no-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.

Referee Report

1 major / 0 minor

Summary. The paper claims that it is NP-hard to determine whether a given graph admits a min-1-planar drawing. A drawing is min-1-planar if for every crossing at least one of the two edges is involved in at most one crossing total. The result is obtained via a polynomial-time reduction from a known NP-hard problem and generalizes the notion of k-planarity introduced in prior work.

Significance. If correct, the result would establish the first NP-hardness result for the min-k-planarity family, providing a complexity baseline for this relaxed crossing condition and potentially informing algorithmic work on bounded-crossing drawings.

major comments (1)
  1. [Abstract] Abstract: the claim is stated but the manuscript supplies no reduction, no proof sketch, and no verification that the reduction preserves the min-1-planarity property; the central claim cannot be checked from the available text.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review. We address the single major comment below, noting that the full manuscript contains the requested details even if the abstract does not.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim is stated but the manuscript supplies no reduction, no proof sketch, and no verification that the reduction preserves the min-1-planarity property; the central claim cannot be checked from the available text.

    Authors: The abstract is a concise summary and therefore contains only the high-level claim, which is standard practice. The manuscript itself supplies the polynomial-time reduction from a known NP-hard problem, the proof sketch, and the verification that the construction preserves the min-1-planarity property; these appear in the sections following the abstract. The central claim is therefore verifiable from the complete manuscript text. revision: no

Circularity Check

0 steps flagged

No significant circularity; standard external reduction

full rationale

The paper establishes NP-hardness of min-1-planarity via a polynomial-time reduction from a known NP-hard problem (standard complexity-theoretic technique). The definition of min-1-planarity is imported from independent prior work by Binucci et al. (GD 2023), not defined in terms of the hardness result itself. No equations, parameters, or self-citations reduce the central claim to its own inputs by construction. The derivation chain is self-contained against external benchmarks and contains no self-definitional, fitted-prediction, or load-bearing self-citation steps.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the existence of a valid reduction proof, which is not supplied; relies on standard definitions of NP-hardness and the external definition of min-k-planarity.

axioms (1)
  • standard math NP-hardness is established via polynomial-time many-one reduction from a known NP-complete problem
    Implicit in any NP-hardness claim; invoked by the statement that the decision problem is NP-hard.

pith-pipeline@v0.9.0 · 5627 in / 1012 out tokens · 44143 ms · 2026-05-25T06:41:16.171916+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · 1 internal anchor

  1. [1]

    A Geometric Heuristic for Rectilinear Crossing Minimization

    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, 2021.doi:10.1137/1. 9...

    work page doi:10.1137/1 2021

  2. [2]

    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

  3. [3]

    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

  4. [4]

    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

  5. [5]

    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

  6. [6]

    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

  7. [7]

    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

  8. [8]

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

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

  9. [9]

    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

  10. [10]

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

    work page doi:10.1016/j.orl.2008.05.004 2008

  11. [11]

    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 internal anchor Pith review doi:10.4230/lipics.gd.2024.25 2024

  12. [12]

    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 Y. Okada 13 Drawing, 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18-20,

    work page doi:10.1016/j.ipl.2020.106083 2020

  13. [13]

    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

  14. [14]

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

    work page 2007