Abstract
We give an O(φk · n2) fixed parameter tractable algorithm for the 1-Sided Crossing Minimization. The constant φ in the running time is the golden ratio φ = (1+√5)/2 ≈ 1.618. The constant k is the parameter of the problem: the number of allowed edge crossings.
Similar content being viewed by others
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Dujmovic, V., Whitesides, S. An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization. Algorithmica 40, 15–31 (2004). https://doi.org/10.1007/s00453-004-1093-2
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-004-1093-2