<div class="csl-bib-body">
<div class="csl-entry">Dobler, A. (2025). A note on the complexity of one-sided crossing minimization of trees. <i>Information Processing Letters</i>, <i>190</i>, Article 106575. https://doi.org/10.1016/j.ipl.2025.106575</div>
</div>
-
dc.identifier.issn
0020-0190
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/225221
-
dc.description.abstract
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.
en
dc.language.iso
en
-
dc.publisher
ELSEVIER
-
dc.relation.ispartof
Information Processing Letters
-
dc.subject
Graph drawing
en
dc.subject
NP-hardness
en
dc.subject
One-sided crossing minimization
en
dc.title
A note on the complexity of one-sided crossing minimization of trees
