Name
Abstract | ||
|---|---|---|
In this paper we consider a new problem that occurs when drawing wiring diagrams or public transportation networks. Given an embedded graph G = (V, E) (e.g., the streets served by a bus network) and a set L of paths in G (e.g., the bus lines), we want to draw the paths along the edges of G such that they cross each other as few times as possible. For esthetic reasons we insist that the relative order of the paths that traverse a node does not change within the area occupied by that node. Our main contribution is an algorithm that minimizes the number of crossings on a single edge {u, v} ∈ E if we are given the order of the incoming and outgoing paths. The difficulty is deciding the order of the paths that terminate in u or v with respect to the fixed order of the paths that do not end there. Our algorithm uses dynamic programming and takes O(n2) time, where n is the number of terminating paths. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/978-3-540-70904-6_27 | Graph Drawing |
Keywords | Field | DocType |
main contribution,relative order,wiring diagram,esthetic reason,outgoing path,bus line,intra-edge crossing,new problem,dynamic programming,embedded graph,public transportation map,fixed order,bus network,public transport | Dynamic programming,Discrete mathematics,Graph,Combinatorics,Bus network,Computer science,Public transport,Wiring diagram,Floyd–Warshall algorithm,Normalization property,Traverse | Conference |
Volume | ISSN | Citations |
4372 | 0302-9743 | 12 |
PageRank | References | Authors |
0.85 | 3 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marc Benkert | 1 | 200 | 14.45 |
| Martin Nöllenburg | 2 | 12 | 0.85 |
| Takeaki Uno | 3 | 1319 | 107.99 |
| Alexander Wolff | 4 | 222 | 22.66 |