pith. sign in

arxiv: 2510.00331 · v3 · submitted 2025-09-30 · 💻 cs.DS

One-Sided Local Crossing Minimization

Panos Giannopoulos , Miriam Goetze , Grzegorz Gutowski , Maarten L\"offler , Martin N\"ollenburg , Yuto Okada , Jonathan Rollin , Birgit Vogtenhuber
show 1 more author
Alexander Wolff
This is my paper

Pith reviewed 2026-05-18 10:54 UTC · model grok-4.3

classification 💻 cs.DS
keywords graph drawingcrossing minimizationNP-hardnesslocal crossingsstar forestsapproximation algorithmsExponential-Time Hypothesis
0
0 comments X p. Extension

The pith

One-sided local crossing minimization is NP-hard even when restricted to forests of high-degree stars.

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

The paper proves that minimizing the maximum number of crossings per edge in a one-sided bipartite drawing remains NP-hard for the restricted case of star forests with high maximum degree. This confirms a recent conjecture and adds a tight conditional lower bound: assuming the Exponential-Time Hypothesis, no subexponential-time algorithm exists for these instances. For the easier special case of forests where every star has degree at most 2, the authors supply an exact quadratic-time algorithm. They also adapt the classical median heuristic with a new tie-breaking rule and prove that it still achieves a 3-approximation ratio in the local-crossing setting. The results tighten our understanding of the complexity landscape inside the Sugiyama framework for layered graph drawing.

Core claim

The central claim is that one-sided local crossing minimization is NP-hard even for forests of high-degree stars. The proof proceeds by a polynomial-time reduction that constructs star-forest instances in which the maximum crossings per edge in any ordering exactly encodes the solution to the source NP-hard problem. The same reduction yields a tight lower bound under the Exponential-Time Hypothesis, ruling out subexponential algorithms. In contrast, when every star has degree at most two the problem admits a quadratic-time exact algorithm, and a suitably modified median heuristic guarantees a 3-approximation for general instances.

What carries the argument

A polynomial-time reduction from a known NP-hard problem to star-forest instances that encodes the optimum via maximum crossings per edge.

If this is right

  • The problem stays NP-hard on sparse graphs consisting only of stars.
  • No 2^{o(n)} algorithm exists for these star-forest instances under ETH.
  • A simple quadratic algorithm solves the special case of degree-at-most-2 stars exactly.
  • The median heuristic with the new tie-breaking rule still guarantees a 3-approximation ratio.

Where Pith is reading between the lines

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

  • Similar reductions may show hardness for other local optimization problems in layered drawings.
  • Parameterized algorithms by maximum degree or number of stars become natural next targets.
  • The 3-approximation might extend to two-sided local crossing minimization with additional work.

Load-bearing premise

The constructed star-forest instances preserve the maximum crossings per edge exactly as the solution to the source problem.

What would settle it

A subexponential-time algorithm for one-sided local crossing minimization on star forests with unbounded degree, or a polynomial-time algorithm for the same problem.

read the original abstract

Drawing graphs with the minimum number of crossings is a classical problem that has been studied extensively. Many restricted versions of the problem have been considered. For example, bipartite graphs can be drawn such that the two sets in the bipartition of the vertex set are mapped to two parallel lines, and the edges are drawn as straight-line segments. In this setting, the number of crossings depends only on the ordering of the vertices on the two lines. Two natural variants of the problem have been studied. In the one-sided case, the order of the vertices on one of the two lines is given and fixed; in the two-sided case, no order is given. Both cases are important yet NP-hard subproblems in the so-called Sugiyama framework for drawing layered graphs with few crossings. For the one-sided case, Eades and Wormald [Algorithmica 1994] introduced a median heuristic and showed that it has an approximation ratio of 3. In recent years, researchers have focused on a local version of crossing minimization, where the aim is to minimize the maximum number of crossings per edge instead of the total number of crossings. Kobayashi, Okada, and Wolff [SoCG 2025] investigated the complexity of local crossing minimization parameterized by the natural parameter. They conjectured that one-sided local crossing minimization is NP-hard. In this work, we confirm their conjecture by showing that the problem is NP-hard even for forests of high-degree stars. In fact, more strongly, the reduction yields a tight lower bound, which excludes the existence of subexponential-time algorithms assuming the Exponential-Time Hypothesis. In contrast, we present a quadratic-time algorithm for the special case of forests of stars of maximum degree 2. Finally, we provide a median heuristic with a carefully designed tie-breaking scheme and prove that it has an approximation ratio of 3 in the local setting.

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 / 2 minor

Summary. The paper proves NP-hardness of one-sided local crossing minimization even for forests of high-degree stars, with the reduction also yielding an ETH-based lower bound ruling out subexponential-time algorithms. It gives a quadratic-time algorithm for the special case of degree-2 stars and proves a 3-approximation ratio for a median heuristic with a designed tie-breaking scheme.

Significance. If the reduction holds, the result confirms the conjecture of Kobayashi et al. and strengthens it with a tight ETH bound, which is a solid contribution to the complexity landscape of local crossing minimization in the Sugiyama framework. The contrast with the polynomial algorithm for low-degree stars usefully isolates the role of degree, and the approximation result extends prior median-heuristic analysis to the local objective.

major comments (1)
  1. [§3] §3 (Hardness reduction): The polynomial-time reduction from a known NP-hard problem to star-forest instances must ensure that the maximum crossings per edge in any ordering is at most k if and only if the source instance is yes. The construction needs to be verified to show that the high-degree star centers and leaves force crossings to encode the source solution exactly, with no alternative ordering of the fixed side achieving a strictly lower max-crossings value that would bypass the hardness. This encoding is load-bearing for both the NP-hardness claim and the ETH-tight lower bound (which further requires linear or subexponential size preservation).
minor comments (2)
  1. [Abstract] The abstract and introduction could explicitly name the source problem used in the reduction for improved readability.
  2. [Figures] Ensure all figures illustrating star-forest instances clearly label the fixed ordering side and crossing counts.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough review and positive assessment of our work. We address the major comment on the hardness reduction below.

read point-by-point responses

  1. Referee: [§3] §3 (Hardness reduction): The polynomial-time reduction from a known NP-hard problem to star-forest instances must ensure that the maximum crossings per edge in any ordering is at most k if and only if the source instance is yes. The construction needs to be verified to show that the high-degree star centers and leaves force crossings to encode the source solution exactly, with no alternative ordering of the fixed side achieving a strictly lower max-crossings value that would bypass the hardness. This encoding is load-bearing for both the NP-hardness claim and the ETH-tight lower bound (which further requires linear or subexponential size preservation).

    Authors: We appreciate the referee's emphasis on the correctness of the reduction in Section 3. The manuscript details a polynomial-time reduction from a known NP-hard problem to instances consisting of forests of high-degree stars. In the proofs accompanying the construction (Theorems 3.1 and 3.2), we show the equivalence: there is an ordering of the free side with maximum crossings per edge ≤ k if and only if the source instance is a yes-instance. The high-degree star centers and their leaves are arranged so that the crossings on each edge are determined by the relative ordering of the leaves attached to different centers, encoding the solution exactly. We demonstrate that any ordering achieving the bound must correspond to a valid solution to the source problem, and that alternative orderings cannot yield a strictly smaller maximum without violating the encoding, due to the multiplicity of crossings induced by high degrees. Regarding the ETH lower bound, the reduction preserves linear size, as required to rule out subexponential algorithms. The lemmas in the section verify this encoding rigorously. revision: no

Circularity Check

0 steps flagged

No circularity: NP-hardness via independent reduction from established problem

full rationale

The paper establishes NP-hardness of one-sided local crossing minimization for forests of high-degree stars through a polynomial-time reduction from a known NP-hard problem (likely 3-SAT or similar, per standard complexity arguments). This reduction constructs star-forest instances such that the maximum crossings per edge in the ordering directly encodes satisfiability, with the ETH-tight bound following from linear-size preservation. No derivation step defines a quantity in terms of itself, renames a fitted parameter as a prediction, or relies on a self-citation chain for the core claim; the prior conjecture citation merely motivates the result and is not used to justify the reduction's correctness. The quadratic algorithm for degree-2 stars and the median heuristic approximation are independent of the hardness proof and contain no self-referential equations. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard complexity-theoretic assumptions for reductions and on the definition of local crossing number; no free parameters or new entities are introduced.

axioms (1)
  • standard math NP-hardness of the source problem used in the reduction (standard in complexity proofs)
    The hardness proof is obtained by polynomial-time reduction from an established NP-hard problem.

pith-pipeline@v0.9.0 · 5904 in / 1167 out tokens · 45674 ms · 2026-05-18T10:54:07.755198+00:00 · methodology

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

13 extracted references · 13 canonical work pages

  1. [1]

    Eliminating crossings in ordered graphs

    1 Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Roohani Sharma, Yushi Uno, and Alexander Wolff. Eliminating crossings in ordered graphs. In Hans Bodlaender, editor,19th Scand. Symp. Algorithm Theory (SW AT), volume 294 ofLIPIcs, pages 1:1–1:19. Schloss Dagstuhl – Leibniz-Institut für Informatik, 2024.doi:10.4230/LIPIcs.SWAT.2024.1. G....

    work page doi:10.4230/lipics.swat.2024.1 2024

  2. [2]

    3 Christopher Auer, Christian Bachmaier, Franz J

    URL:https://arxiv.org/abs/2008.09329, doi:10.1093/comjnl/ bxad038. 3 Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, and Josef Reislhuber. Outer 1-planar graphs.Algorithmica, 74(4):1293–1320, 2016.doi:10.1007/S00453-015-0002-1. 4 Michael Bannister and David Eppstein. Crossing minimization fo...

    work page doi:10.1093/comjnl/ 2008

  3. [3]

    6 Carla Binucci, Walter Didimo, and Fabrizio Montecchiani

    doi:10.1007/978-3-540-30559-0_28. 6 Carla Binucci, Walter Didimo, and Fabrizio Montecchiani. 1-planarity testing and embedding: An experimental study.Computational Geometry, 108:101900,

    work page doi:10.1007/978-3-540-30559-0_28

  4. [4]

    2022.101900

    doi:10.1016/j.comgeo. 2022.101900. 7 Susanna Caroppo, Giordano Da Lozzo, and Giuseppe Di Battista. Quantum algorithms for one-sided crossing minimization.Theoretical Computer Science, 1052:115424,

    work page doi:10.1016/j.comgeo 2022

  5. [5]

    8 Steven Chaplick, Myroslav Kryven, Giuseppe Liotta, Andre Löffler, and Alexander Wolff

    doi: 10.1016/j.tcs.2025.115424. 8 Steven Chaplick, Myroslav Kryven, Giuseppe Liotta, Andre Löffler, and Alexander Wolff. Beyond outerplanarity. In Fabrizio Frati and Kwan-Liu Ma, editors,25th Int. Symp. Graph Drawing & Network Vis. (GD), volume 10692 ofLNCS, pages 546–559. Springer,

    work page doi:10.1016/j.tcs.2025.115424 2025

  6. [6]

    9 Vida Dujmović, Henning Fernau, and Michael Kaufmann

    URL: https://arxiv.org/abs/1708.08723,doi:10.1007/978-3-319-73915-1_42. 9 Vida Dujmović, Henning Fernau, and Michael Kaufmann. Fixed parameter algorithms for one-sided crossing minimization revisited.Journal of Discrete Algorithms, 6(2):313–323,

    work page doi:10.1007/978-3-319-73915-1_42

  7. [7]

    10 Peter Eades and Nicholas C

    Selected papers from CompBioNets 2004.doi:10.1016/j.jda.2006.12.008. 10 Peter Eades and Nicholas C. Wormald. Edge crossings in drawings of bipartite graphs. Algorithmica, 11(4):379–403, 1994.doi:10.1007/BF01187020. 11 Simon D. Fink, Miriam Münch, Matthias Pfretzschner, and Ignaz Rutter. Heuristics for exact 1- planarity testing. In Vida Dujmović and Fabri...

    work page doi:10.1016/j.jda.2006.12.008 2004

  8. [8]

    12 Michael R

    To appear. 12 Michael R. Garey and David S. Johnson. Crossing number is NP-complete.SIAM Journal on Algebraic Discrete Methods, 4(3):312–316, 1983.doi:10.1137/0604033. 13 Michael R. Garey, David S. Johnson, and Larry Stockmeyer. Some simplified NP- complete graph problems.Theoretical Computer Science, 1(3):237–267, 1976.doi:10.1016/ 0304-3975(76)90059-1. ...

    work page doi:10.1137/0604033 1983

  9. [9]

    17 Heather Hulett, Todd G

    doi:10.1016/j.jvlc.2014.03.001. 17 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.1016/j.jvlc.2014.03.001 2014

  10. [10]

    Multigraph realizations of degree sequences: Maximization is easy, minimization is hard

    doi:10.1016/J.ORL.2008.05.004. 18 Michael Jünger and Petra Mutzel. 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms.Journal of Graph Algorithms and Applications, 1(1):1–25, 1997.doi:10.7155/jgaa.00001. 12 One-Sided Local Crossing Minimization 19 Paul C. Kainen. The book thickness of a graph. II. In20th Southeastern...

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

  11. [11]

    A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Path

    20 Yasuaki Kobayashi, Hiromu Ohtsuka, and Hisao Tamaki. An improved fixed-parameter algorithm for one-page crossing minimization. In Daniel Lokshtanov and Naomi Nishimura, editors,12th Int. Symp. Paramet. & Exact Comput. (IPEC), volume 89 ofLIPIcs, pages 25:1–25:12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017.doi:10.4230/LIPICS. IPEC.2017.25. ...

    work page doi:10.4230/lipics 2017

  12. [12]

    27 Marcus Schaefer

    doi:10.1007/3-540-63938-1\_67. 27 Marcus Schaefer. The graph crossing number and its variants: A survey.Electronic Journal of Combinatorics, DS21, 2024.doi:10.37236/2713. 28 Kozo Sugiyama, Shojiro Tagawa, and Mitsuhiko Toda. Methods for visual understanding of hierarchical system structures.IEEE Trans. Syst. Man Cybern., 11(2):109–125,

    work page doi:10.1007/3-540-63938-1 2024

  13. [13]

    doi:10.1109/TSMC.1981.4308636

    work page doi:10.1109/tsmc.1981.4308636 1981