Edges and switches, tunnels and bridges

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

4 Citaten (Scopus)
77 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.
Originele taal-2Engels
TitelProceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada
RedacteurenF. Dehne, J.R. Sack, N. Zeh
Plaats van productieBerlin, Germany
ISBN van geprinte versie978-3-540-73948-7
StatusGepubliceerd - 2007
Evenement10th International Symposium on Algorithms and Data Structures (WADS 2007) - Halifax, Canada
Duur: 15 aug 200717 aug 2007
Congresnummer: 10

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Congres10th International Symposium on Algorithms and Data Structures (WADS 2007)
Verkorte titelWADS 2007
AnderWADS 2007, Halifax, Nova Scotia, Canada


Duik in de onderzoeksthema's van 'Edges and switches, tunnels and bridges'. Samen vormen ze een unieke vingerafdruk.

Citeer dit