Pith. sign in

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

· 2023 · cs.CC · arXiv 2306.15339

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
open full Pith review browse 1 citing papers arXiv PDF
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.

fields

cs.DS 1

years

2024 1

verdicts

CONDITIONAL 1

representative citing papers

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

cs.DS · 2024-12-05 · conditional · novelty 7.0

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.

citing papers explorer

Showing 1 of 1 citing paper.

  • Recognizing 2-Layer and Outer $k$-Planar Graphs cs.DS · 2024-12-05 · conditional · none · ref 20 · internal anchor

    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.