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)
73 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
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
PublisherSpringer
Pages77-88
ISBN (Print)978-3-540-73948-7
DOIs
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
Volume4619
ISSN (Print)0302-9743

Conference

Conference10th International Symposium on Algorithms and Data Structures (WADS 2007)
Abbreviated titleWADS 2007
CountryCanada
CityHalifax
Period15/08/0717/08/07
OtherWADS 2007, Halifax, Nova Scotia, Canada

Fingerprint

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

Cite this