Edges and switches, tunnels and bridges

D. Eppstein, M.J. Kreveld, van, E. Mumford, B. Speckmann

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)
1 Downloads (Pure)

Abstract

Edge casing is a well-known method to improve the readability of drawings of non-planar graphs. A cased drawing orders the edges of each edge crossing and interrupts the lower edge in an appropriate neighborhood of the crossing. Certain orders will lead to a more readable drawing than others. We formulate several optimization criteria that try to capture the concept of a "good" cased drawing. Further, we address the algorithmic question of how to turn a given drawing into an optimal cased drawing. For many of the resulting optimization problems, we either find polynomial time algorithms or NP-hardness results.
Original languageEnglish
Pages (from-to)790-802
JournalComputational Geometry
Volume42
Issue number8
DOIs
Publication statusPublished - 2009

Fingerprint Dive into the research topics of 'Edges and switches, tunnels and bridges'. Together they form a unique fingerprint.

Cite this