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 language | English |
---|---|
Title of host publication | Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada |
Editors | F. Dehne, J.R. Sack, N. Zeh |
Place of Publication | Berlin, Germany |
Publisher | Springer |
Pages | 77-88 |
ISBN (Print) | 978-3-540-73948-7 |
DOIs | |
Publication status | Published - 2007 |
Event | 10th International Symposium on Algorithms and Data Structures (WADS 2007) - Halifax, Canada Duration: 15 Aug 2007 → 17 Aug 2007 Conference number: 10 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Volume | 4619 |
ISSN (Print) | 0302-9743 |
Conference
Conference | 10th International Symposium on Algorithms and Data Structures (WADS 2007) |
---|---|
Abbreviated title | WADS 2007 |
Country/Territory | Canada |
City | Halifax |
Period | 15/08/07 → 17/08/07 |
Other | WADS 2007, Halifax, Nova Scotia, Canada |