Minimizing Intra-Edge Crossings in Wiring Diagrams and Public Transport Maps

Benkert, Marc and Nöllenburg, Martin and Uno, Takeaki and Wolff, Alexander (2007) Minimizing Intra-Edge Crossings in Wiring Diagrams and Public Transport Maps. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006 , pp. 270-281(Official URL:

Full text not available from this repository.


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} in 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(n^2) time, where n is the number of terminating paths.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-70904-6_27
Classifications: G Algorithms and Complexity > G.420 Crossings
P Styles > P.600 Poly-line

Actions (login required)

View Item View Item