pith. sign in

arxiv: 1907.01243 · v1 · pith:IPMTSM5Unew · submitted 2019-07-02 · 💻 cs.CG · cs.DS

Geometric Crossing-Minimization -- A Scalable Randomized Approach

Marcel Radermacher , Ignaz Rutter This is my paper

Pith reviewed 2026-05-25 10:33 UTC · model grok-4.3

classification 💻 cs.CG cs.DS
keywords crossing minimizationgeometric graphsrandomized algorithmsapproximation algorithmsgraph drawingco-crossing numbervertex optimization
0
0 comments X

The pith

A random subset of Θ(k log k) edges approximates the co-crossing number of a degree-k vertex by any fixed factor with high probability.

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

The paper develops a randomized method to minimize crossings in straight-line drawings of graphs by repositioning each vertex to a position that is optimal only with respect to a small random sample of edges. This speeds up the basic operation of finding a crossing-minimal vertex position enough to handle graphs with thousands of edges. Under the condition that crossings per edge-position pair are o(|E|), the sample size guarantees a constant-factor approximation to the true best position with high probability. Experiments on instances up to 13,000 edges show substantial crossing reductions, with strategy choice depending on degree distribution. The work extends practical geometric crossing minimization beyond the previous limit of 200 edges.

Core claim

In drawings where each edge uv and position p for v has o(|E|) crossings, sampling Θ(k log k) edges allows approximating the co-crossing number of a degree-k vertex v by an arbitrary fixed factor δ with high probability.

What carries the argument

Random edge subset sampling to approximate the co-crossing number used for determining near-optimal vertex positions.

If this is right

  • Crossing minimization heuristics become applicable to geometric graphs with a few thousand edges.
  • The approximation factor δ can be made arbitrarily close to 1 by adjusting the sample size constant.
  • Practical running times improve by a factor of about 20 from the basic single-vertex move operation.
  • Different sampling or selection strategies perform best depending on the graph's degree distribution.
  • Total number of crossings can be reduced considerably without requiring exact optimality for each vertex move.

Where Pith is reading between the lines

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

  • The sampling approach could be iterated multiple times or combined with local search for further improvements on very large graphs.
  • Graphs from real applications may naturally satisfy the o(|E|) crossings condition, making the guarantee applicable without modification.
  • Similar randomized sampling might accelerate other geometric optimization tasks that involve counting interactions between line segments.

Load-bearing premise

Drawings have the property that no single edge crosses o(|E|) times with any fixed position of one of its endpoints.

What would settle it

Construct a drawing violating the o(|E|) crossings condition and verify that the random subset fails to approximate the co-crossing number within factor δ.

read the original abstract

We consider the minimization of edge-crossings in geometric drawings of graphs $G=(V, E)$, i.e., in drawings where each edge is depicted as a line segment. The respective decision problem is NP-hard [Bienstock, '91]. In contrast to theory and the topological setting, the geometric setting did not receive a lot of attention in practice. Prior work [Radermacher et al., ALENEX'18] is limited to the crossing-minimization in geometric graphs with less than $200$ edges. The described heuristics base on the primitive operation of moving a single vertex $v$ to its crossing-minimal position, i.e., the position in $\mathbb{R}^2$ that minimizes the number of crossings on edges incident to $v$. In this paper, we introduce a technique to speed-up the computation by a factor of $20$. This is necessary but not sufficient to cope with graphs with a few thousand edges. In order to handle larger graphs, we drop the condition that each vertex $v$ has to be moved to its crossing-minimal position and compute a position that is only optimal with respect to a small random subset of the edges. In our theoretical contribution, we consider drawings that contain for each edge $uv \in E$ and each position $p \in \mathbb{R}^2$ for $v$ $o(|E|)$ crossings. In this case, we prove that with a random subset of the edges of size $\Theta(k \log k)$ the co-crossing number of a degree-$k$ vertex $v$, i.e., the number of edge pairs $uv \in E, e \in E$ that do not cross, can be approximated by an arbitrary but fixed factor $\delta$ with high probability. In our experimental evaluation, we show that the randomized approach reduces the number of crossings in graphs with up to $13\,000$ edges considerably. The evaluation suggests that depending on the degree-distribution different strategies result in the fewest number of crossings.

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

2 major / 2 minor

Summary. The paper introduces a randomized sampling heuristic to accelerate crossing minimization in geometric straight-line drawings of graphs. It claims a 20x speedup over prior exact-per-vertex methods (limited to <200 edges) by moving each vertex v only to a position optimal w.r.t. a random subset of Θ(k log k) edges for a degree-k vertex. Under the assumption that every edge participates in o(|E|) crossings at every candidate position for its endpoint, the manuscript proves that this sample yields a (1±δ)-approximation to the co-crossing number with high probability. Experiments on instances with up to 13 000 edges report considerable crossing reductions, with strategy choice depending on degree distribution.

Significance. If the empirical reductions hold and the sampling heuristic scales reliably, the work meaningfully extends practical geometric crossing minimization from hundreds to thousands of edges. The conditional probabilistic guarantee and the independent experimental evaluation on larger graphs are both positive contributions; the latter in particular demonstrates practical utility beyond the theoretical premise.

major comments (2)
  1. [Abstract / theoretical contribution] Abstract / theoretical contribution: the probabilistic (1±δ) approximation guarantee for the co-crossing number is derived under the explicit premise that every edge uv and every position p of v participates in o(|E|) crossings. The experimental section provides no verification or measurement that the initial drawings or any intermediate placements on the tested graphs (up to 13 000 edges) satisfy this density condition. Without such a check, the theoretical analysis does not apply to the reported runs, leaving the claimed speedup supported only by empirical observation.
  2. [Experimental evaluation] Experimental evaluation: the manuscript reports that different sampling strategies yield the fewest crossings depending on degree distribution, yet no quantitative breakdown (e.g., per-graph crossing counts, baseline comparisons to the ALENEX'18 method, or statistical significance) is supplied to substantiate the “considerably” reduced crossing numbers or the 20x speedup claim.
minor comments (2)
  1. [Abstract] Notation: the term “co-crossing number” is introduced without an explicit equation or definition in the abstract; a formal definition (e.g., |{e : uv and e do not cross}|) should appear early in the text.
  2. [Abstract] The manuscript should clarify whether the o(|E|) assumption is intended only for the theoretical result or is also claimed to hold for the experimental instances.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. Below we respond point by point to the major concerns, distinguishing the conditional theoretical result from the empirical evaluation and committing to added quantitative detail where appropriate.

read point-by-point responses

  1. Referee: [Abstract / theoretical contribution] the probabilistic (1±δ) approximation guarantee for the co-crossing number is derived under the explicit premise that every edge uv and every position p of v participates in o(|E|) crossings. The experimental section provides no verification or measurement that the initial drawings or any intermediate placements on the tested graphs (up to 13 000 edges) satisfy this density condition. Without such a check, the theoretical analysis does not apply to the reported runs, leaving the claimed speedup supported only by empirical observation.

    Authors: The referee is correct that the (1±δ) guarantee is conditional on the stated o(|E|) crossing-density assumption and that the experimental section contains no explicit verification of this condition on the tested instances. The manuscript presents the probabilistic analysis as a conditional theoretical contribution and the experiments as an independent empirical demonstration of practical scaling; it does not assert that the guarantee applies to the reported runs. In revision we will add an explicit statement clarifying this separation together with a short empirical check (e.g., average crossings per edge across the test set) to indicate whether the low-density regime appears to hold in practice. revision: partial

  2. Referee: [Experimental evaluation] the manuscript reports that different sampling strategies yield the fewest crossings depending on degree distribution, yet no quantitative breakdown (e.g., per-graph crossing counts, baseline comparisons to the ALENEX'18 method, or statistical significance) is supplied to substantiate the “considerably” reduced crossing numbers or the 20x speedup claim.

    Authors: We agree that the experimental claims would be more convincing with additional quantitative support. The current text summarizes aggregate outcomes; the revision will incorporate per-graph tables of crossing counts before and after optimization, explicit runtime comparisons against the ALENEX'18 baseline on all instances small enough for the exact method to finish, and a note on the number of independent runs performed so that readers can assess variability and statistical reliability of the reported speedups and crossing reductions. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper states an explicit assumption (o(|E|) crossings per edge-position pair) and derives a probabilistic approximation guarantee for the co-crossing number via random sampling of size Θ(k log k). This is a standard concentration argument (e.g., via Chernoff or similar bounds) that does not reduce to its inputs by construction, self-definition, or fitted parameters. Experiments are reported as independent empirical observations on crossing reduction for graphs up to 13k edges and do not invoke the theoretical guarantee. No load-bearing self-citations, uniqueness theorems, or ansatzes are used in the central claims.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on the standard NP-hardness result and a domain-specific density assumption for the sampling analysis; no free parameters, invented entities, or ad-hoc constants are introduced.

axioms (2)
  • standard math The decision problem of minimizing crossings in geometric drawings is NP-hard (Bienstock, '91)
    Cited as background establishing computational difficulty.
  • domain assumption Drawings contain o(|E|) crossings for each edge uv and each candidate position p of v
    Invoked to obtain the high-probability approximation bound for the random subset.

pith-pipeline@v0.9.0 · 5908 in / 1294 out tokens · 50397 ms · 2026-05-25T10:33:52.652411+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

  1. [2]

    6 Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger, and Petra Mutzel

    doi:10.1007/BF02574701. 6 Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger, and Petra Mutzel. Crossings and Planarization. In Roberto Tamassia, editor,Handbook of Graph Drawing and Visualization, chapter 2, pages 43–85. Chapman and Hall/CRC,

    work page doi:10.1007/bf02574701

  2. [3]

    Inserting Multiple Edges into a Planar Graph

    8 Markus Chimani and Petr Hlinený. Inserting Multiple Edges into a Planar Graph. In Sándor Fekete and Anna Lubiw, editors,Proceedings of the 32nd Annual Symposium on Computational Geometry (SoCG’16), volume 51 ofLeibniz International Proceedings in Informatics (LIPIcs) , pages 30:1–30:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016.doi:10.4230/...

    work page 2016

  3. [4]

    10 Almut Demel, Dominik Dürrschnabel, Tamara Mchedlidze, Marcel Radermacher, and Lasse Wulf

    doi:10.1145/2049662.2049663. 10 Almut Demel, Dominik Dürrschnabel, Tamara Mchedlidze, Marcel Radermacher, and Lasse Wulf. A Greedy Heuristic for Crossing-Angle Maximization. In Proceedings of the 26th International Symposium on Graph Drawing (GD’18) , Lecture Notes in Computer Science, pages 286–299,

    work page doi:10.1145/2049662.2049663

  4. [5]

    11 Ruy Fabila-Monroy and Jorge López

    doi:10.1007/978-3-030-04414-5\_20. 11 Ruy Fabila-Monroy and Jorge López. Computational Search of Small Point Sets with Small Rectilinear Crossing Number. Journal of Graph Algorithms and Applications , 18(3):393–399,

    work page doi:10.1007/978-3-030-04414-5

  5. [6]

    12 Emden R

    doi:10.7155/jgaa.00328. 12 Emden R. Gansner, Yehuda Koren, and Stephen North. Graph Drawing by Stress Major- ization. In János Pach, editor,Proceedings of the 12th International Symposium on Graph Drawing (GD’04), volume 3383 ofLecture Notes in Computer Science , pages 239–250. Springer Berlin/Heidelberg,

    work page doi:10.7155/jgaa.00328

  6. [7]

    13 Michael R

    doi:10.1007/978-3-540-31843-9\_25. 13 Michael R. Garey and David S. Johnson. Crossing Number is NP-Complete.SIAM Journal on Algebraic and Discrete Methods , 4(3):312–316,

    work page doi:10.1007/978-3-540-31843-9

  7. [8]

    15 Sariel Har-Peled and Micha Sharir

    doi:10.1007/s00453-004-1128-8. 15 Sariel Har-Peled and Micha Sharir. Relative(p,ϵ )-Approximations in Geometry.Discrete & Computational Geometry, 45(3):462–496,

    work page doi:10.1007/s00453-004-1128-8

  8. [9]

    16 Stephen G

    doi:10.1007/s00454-010-9248-1. 16 Stephen G. Kobourov. Force-Directed Drawing Algorithms. In Roberto Tamassia, editor, Handbook of Graph Drawing and Visualization , chapter

    work page doi:10.1007/s00454-010-9248-1

  9. [10]

    Long, and Aravind Srinivasan

    17 Yi Li, Philip M. Long, and Aravind Srinivasan. Improved Bounds on the Sample Complexity of Learning. Journal of Computer and System Sciences , 62(3):516 – 527, 2001.doi:10.1006/ jcss.2000.1741. 16 Geometric Crossing Minimization 18 Jiří Matoušek. Lectures on Discrete Geometry, volume

    work page arXiv 2001

  10. [11]

    20 Thomas L

    doi:10.1109/TVCG.2017.2689016. 20 Thomas L. Moore. Using Euler’s Formula to Solve Plane Separation Problems.The College Mathematics Journal, 22(2):125–130,

    work page doi:10.1109/tvcg.2017.2689016 2017

  11. [12]

    A Geometric Heuristic for Rectilinear Crossing Minimization

    21 Marcel Radermacher, Klara Reichard, Ignaz Rutter, and Dorothea Wagner. A Geometric Heuristic for Rectilinear Crossing Minimization. In Proceedings of the 20th Workshop on Algorithm Engineering and Experiments (ALENEX’18) , pages 129–138, 2018.doi:10.1137/1. 9781611975055.12. 22 David J. Sheskin.Handbook of Parametric and Nonparametric Statistical Proce...

    work page doi:10.1137/1 2018