Pith. sign in

REVIEW 2 cited by

A Note on the Complexity of One-Sided Crossing Minimization of Trees

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2306.15339 v1 pith:N26ZVD3G submitted 2023-06-27 cs.CC

Alexander Dobler This is my paper · ORCID
classification cs.CC
keywords crossingminimizationone-sidedtreesalgorithmcomplexitycounterexampleharrigan
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

In 2011, Harrigan and Healy published a polynomial-time algorithm for one-sided crossing minimization for trees. We point out a counterexample to that algorithm, and show that one-sided crossing minimization is NP-hard for trees.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Recognizing 2-Layer and Outer $k$-Planar Graphs

    cs.DS 2024-12 conditional novelty 7.0 of 10

    The paper gives XP algorithms for recognizing 2-layer and outer k-planar graphs, proves both problems XNLP-hard, and gives an FPT algorithm for the one-sided 2-layer variant.

  2. Arcee: An OCM-Solver

    cs.DS 2024-11 conditional novelty 4.0 of 10

    Arcee is a PACE 2024 OCM solver combining penalty-graph SCC splitting, Dujmovic-style reduction rules, sifting/force-swapping heuristics, and exact FAS-based ILP and branch-and-bound, achieving 4th, 8th, and 4th place...

Pith tools