Home | Issues | About JGAA | Instructions for Authors |
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.
Accepted: August 2010.
Final: August 2010.
Published: November 2010.
Communicated by
Stephen G. Kobourov
|
Journal Supporters
|