Advertisement
Published in:
2013 | OriginalPaper | Chapter
Metro-Line Crossing Minimization: Hardness, Approximations, and Tractable Cases
Authors : Martin Fink, Sergey Pupyrev
Published in: Graph Drawing
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.