Eyal Ackerman, Kevin Buchin, Christiane Knauer, and Günter Rote:

Acyclic orientation of drawings

  1. 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
  2. In: Abstracts of the 22nd European Workshop on Computational Geometry, Delphi, March 2006, pp. 207–210.
  3. Journal of Graph Algorithms and Applications 14, No. 2 (2010), 367–384. doi:10.7155/jgaa.00211


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 problem.

  pdf file (gzipped)
other papers about this subject
Last update: December 15, 2010.