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)

Samenvatting

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
UitgeverijSpringer
Pagina's77-88
ISBN van geprinte versie978-3-540-73948-7
DOI's
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
Volume4619
ISSN van geprinte versie0302-9743

Congres

Congres10th International Symposium on Algorithms and Data Structures (WADS 2007)
Verkorte titelWADS 2007
Land/RegioCanada
StadHalifax
Periode15/08/0717/08/07
AnderWADS 2007, Halifax, Nova Scotia, Canada

Vingerafdruk

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

Citeer dit