Minimizing IntraEdge Crossings in Wiring Diagrams and Public Transport MapsBenkert, Marc and Nöllenburg, Martin and Uno, Takeaki and Wolff, Alexander (2007) Minimizing IntraEdge Crossings in Wiring Diagrams and Public Transport Maps. In: Graph Drawing 14th International Symposium, GD 2006, September 1820, 2006 , pp. 270281(Official URL: http://dx.doi.org/10.1007/9783540709046_27). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540709046_27
AbstractIn 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.
Actions (login required)
