Dobler, A. (2025). A note on the complexity of one-sided crossing minimization of trees. Information Processing Letters, 190, Article 106575. https://doi.org/10.1016/j.ipl.2025.106575
In 2011, Harrigan and Healy claimed that one-sided crossing minimization can be solved in polynomial time on trees [1]. We point out a counterexample to their claims, and show that one-sided crossing minimization is [Figure presented]-hard for trees.
