Acyclic Orientation of Drawings
Eyal Ackerman, Kevin Buchin, Christian Knauer, Günter Rote · Journal of Graph Algorithms and Applications · 2010
Given a set of pseudosegments in the plane or a topological graph, we ask for an orientation of the pseudosegments or edges which induces an acyclic orientation on the corresponding planar map. Depending on the maximum number of crossings on a pseudosegment or an edge, we provide algorithms and hardness proofs for this problem.