Acyclic orientation of drawings

E. Ackerman, K. Buchin, C. Knauer, G. Rote

Research output: Contribution to journalArticleAcademicpeer-review

101 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)367-384
JournalJournal of Graph Algorithms and Applications
Volume14
Issue number2
Publication statusPublished - 2010

Fingerprint

Dive into the research topics of 'Acyclic orientation of drawings'. Together they form a unique fingerprint.

Cite this