Eyal Ackerman, Kevin Buchin, Christiane Knauer, and Günter Rote:
Acyclic orientation of drawings
- In: Proceedings of the 10th Scandinavian Workshop on
Algorithm Theory (SWAT). Riga, July 2006, Editors: Lars Arge
and Rusins Freivalds. Lecture Notes in Computer Science, 4059,
Springer-Verlag, 2006, pp. 266–277. doi:10.1007/11785293_26
In: Abstracts of the 22nd European Workshop on Computational Geometry,
Delphi, March 2006, pp. 207–210.
Journal of Graph Algorithms and Applications
14, No. 2 (2010), 367–384.
Given a set of curves in the plane or a topological graph, we ask for an
orientation of the curves or edges which induces an acyclic orientation on
the corresponding planar map. Depending on the maximum number of crossings on
a curve or an edge, we provide algorithms and hardness proofs for this
Last update: December 15, 2010.