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 single 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. Furthermore, we show that the problem
remains NP-hard on planar graphs even if both the
maximum degree and the number of lines per edge are
bounded by constants; on trees, this restricted
version becomes tractable.
%0 Journal Article
%1 fpw-omlbc-JGAA15
%A Fink, Martin
%A Pupyrev, Sergey
%A Wolff, Alexander
%D 2015
%J Journal of Graph Algorithms & Applications
%K myown
%N 1
%P 111--153
%R 10.7155/jgaa.00351
%T Ordering Metro Lines by Block Crossings
%V 19
%X 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 single 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. Furthermore, we show that the problem
remains NP-hard on planar graphs even if both the
maximum degree and the number of lines per edge are
bounded by constants; on trees, this restricted
version becomes tractable.
@article{fpw-omlbc-JGAA15,
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 single crossings into \emph{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. Furthermore, we show that the problem
remains NP-hard on planar graphs even if both the
maximum degree and the number of lines per edge are
bounded by constants; on trees, this restricted
version becomes tractable.},
added-at = {2024-02-18T09:53:56.000+0100},
author = {Fink, Martin and Pupyrev, Sergey and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/2eb2796718df7d7ea021387f7bfcd1657/awolff},
doi = {10.7155/jgaa.00351},
interhash = {cb9eadd8cbb3bb0a5328e694ea8115d2},
intrahash = {eb2796718df7d7ea021387f7bfcd1657},
journal = {Journal of Graph Algorithms \& Applications},
keywords = {myown},
number = 1,
pages = {111--153},
timestamp = {2024-02-18T12:36:59.000+0100},
title = {Ordering Metro Lines by Block Crossings},
volume = 19,
year = 2015
}