Ordering Metro Lines by Block Crossings
Proc. 38th Int. Sympos. Mathematical Foundations of Computer Science (MFCS'13), volume 8087 of Lecture Notes in Computer Science, page 397-408. Springer-Verlag, (2013)Abstract
A problem that arises in drawings of transportation networks is to minimize the number of crossings between different transportation lines. While this can be done efficiently under specific constraints, not all solutions are visually equivalent. We suggest merging crossings into block crossings, that is, crossings of two neighboring groups of consecutive lines. Unfortunately, minimizing the total number of block crossings is NP-hard even for very simple graphs. We give approximation algorithms for special classes of graphs and an asymptotically worst-case optimal algorithm for block crossings on general graphs.
