Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00211 Acyclic Orientation of Drawings Eyal Ackerman , Kevin Buchin , Christian Knauer , and Günter Rote Vol. 14, no. 2, pp. 367-384, 2010. Regular paper Abstract 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.
|
Submitted: February 2010. Final: August 2010. Published: November 2010. Accepted: August 2010. Communicated by Stephen Kobourov |
Journal of Graph Algorithms and Applications |