Minimizing intra-edge crossings in wiring diagrams and public transport maps

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