Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Metro-Line Crossing Minimization: Hardness, Approximations, and Tractable Cases
verfasst von : Martin Fink, Sergey Pupyrev
Erschienen in: Graph Drawing
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Crossing minimization is one of the central problems in graph drawing. Recently, there has been an increased interest in the problem of minimizing crossings between paths in drawings of graphs. This is the
metro-line crossing minimization
problem (MLCM): Given an embedded graph and a set
L
of simple paths, called
lines
, order the lines on each edge so that the total number of crossings is minimized. So far, the complexity of MLCM has been an open problem. In contrast, the problem variant in which line ends must be placed in outermost position on their edges (MLCM-P) is known to be NP-hard.
Our main results answer two open questions: (i) We show that MLCM is NP-hard. (ii) We give an
$O(\sqrt{\log |L|})$
-approximation algorithm for MLCM-P.