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

2023/06/27 by Alexander Dobler, Dobler, Alexander · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Computational Geometry and Mesh Generation

paper · pdf · doi:10.48550/arxiv.2306.15339

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.

Cited by

• Two-Layer Drawings with a Tree on Top: Vertex Splits and Fixed-Parameter Algorithms
• One-Sided Local Crossing Minimization

Related

• Fixed parameter tractability of crossing minimization of almost-trees
• Crossing Number is NP-hard for Constant Path-width (and Tree-width)
• Block Crossings in One-Sided Tanglegrams
• Cutwidth and Crossings
• One-Sided Local Crossing Minimization