Edges and switches, tunnels and bridges

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
121 Downloads (Pure)


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
Title of host publicationProceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada
EditorsF. Dehne, J.R. Sack, N. Zeh
Place of PublicationBerlin, Germany
ISBN (Print)978-3-540-73948-7
Publication statusPublished - 2007
Event10th International Symposium on Algorithms and Data Structures (WADS 2007) - Halifax, Canada
Duration: 15 Aug 200717 Aug 2007
Conference number: 10

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference10th International Symposium on Algorithms and Data Structures (WADS 2007)
Abbreviated titleWADS 2007
OtherWADS 2007, Halifax, Nova Scotia, Canada


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

Cite this