Edges and switches, tunnels and bridges

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

doi:10.1007/978-3-540-73951-7_8

Edges and switches, tunnels and bridges

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 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	https://doi.org/10.1007/978-3-540-73951-7_8
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	Canada
City	Halifax
Period	15/08/07 → 17/08/07
Other	WADS 2007, Halifax, Nova Scotia, Canada

Access to Document

10.1007/978-3-540-73951-7_8

Metis210766Final published version, 408 KB

Cite this

Eppstein, D., Kreveld, van, M. J., Mumford, E., & Speckmann, B. (2007). Edges and switches, tunnels and bridges. In F. Dehne, J. R. Sack, & N. Zeh (Eds.), Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada (pp. 77-88). (Lecture Notes in Computer Science; Vol. 4619). Springer. https://doi.org/10.1007/978-3-540-73951-7_8

Eppstein, D. ; Kreveld, van, M.J. ; Mumford, E. ; Speckmann, B. / Edges and switches, tunnels and bridges. Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada. editor / F. Dehne ; J.R. Sack ; N. Zeh. Berlin, Germany : Springer, 2007. pp. 77-88 (Lecture Notes in Computer Science).

@inproceedings{0f091bf2448c4d7682828338df7f1d95,

title = "Edges and switches, tunnels and bridges",

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.",

author = "D. Eppstein and {Kreveld, van}, M.J. and E. Mumford and B. Speckmann",

year = "2007",

doi = "10.1007/978-3-540-73951-7_8",

language = "English",

isbn = "978-3-540-73948-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "77--88",

editor = "F. Dehne and J.R. Sack and N. Zeh",

booktitle = "Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada",

address = "Germany",

note = "10th International Symposium on Algorithms and Data Structures (WADS 2007), WADS 2007 ; Conference date: 15-08-2007 Through 17-08-2007",

}

Eppstein, D, Kreveld, van, MJ, Mumford, E & Speckmann, B 2007, Edges and switches, tunnels and bridges. in F Dehne, JR Sack & N Zeh (eds), Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada. Lecture Notes in Computer Science, vol. 4619, Springer, Berlin, Germany, pp. 77-88, 10th International Symposium on Algorithms and Data Structures (WADS 2007), Halifax, Canada, 15/08/07. https://doi.org/10.1007/978-3-540-73951-7_8

Edges and switches, tunnels and bridges. / Eppstein, D.; Kreveld, van, M.J.; Mumford, E.; Speckmann, B.

Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada. ed. / F. Dehne; J.R. Sack; N. Zeh. Berlin, Germany : Springer, 2007. p. 77-88 (Lecture Notes in Computer Science; Vol. 4619).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Edges and switches, tunnels and bridges

AU - Eppstein, D.

AU - Kreveld, van, M.J.

AU - Mumford, E.

AU - Speckmann, B.

N1 - Conference code: 10

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-73951-7_8

DO - 10.1007/978-3-540-73951-7_8

M3 - Conference contribution

SN - 978-3-540-73948-7

T3 - Lecture Notes in Computer Science

SP - 77

EP - 88

BT - Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada

A2 - Dehne, F.

A2 - Sack, J.R.

A2 - Zeh, N.

PB - Springer

CY - Berlin, Germany

T2 - 10th International Symposium on Algorithms and Data Structures (WADS 2007)

Y2 - 15 August 2007 through 17 August 2007

ER -

Eppstein D, Kreveld, van MJ, Mumford E, Speckmann B. Edges and switches, tunnels and bridges. In Dehne F, Sack JR, Zeh N, editors, Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007) 15-17 August 2007, Halifax, Nova Scotia, Canada. Berlin, Germany: Springer. 2007. p. 77-88. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-540-73951-7_8

Edges and switches, tunnels and bridges

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this