Metro-line crossing minimization: hardness, approximations, and tractable cases

DOI10.1007/978-3-319-03841-4_29MaRDI QIDQ2867669zbMATH OpenOpenAlexFDO

Authors Martin Fink, Sergey Pupyrev

Publication date 20 December 2013

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.2079

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Abstract: 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(sqrtlog|L|)$-approximation algorithm for MLCM-P.

Recommendations

• On metro-line crossing minimization
• Two Polynomial Time Algorithms for the Metro-line Crossing Minimization Problem
• Line Crossing Minimization on Metro Maps
• An improved algorithm for the metro-line crossing minimization problem
• Ordering metro lines by block crossings

Cited in

(8)

• Edge routing with ordered bundles
• Line Crossing Minimization on Metro Maps
• On metro-line crossing minimization
• Ordering metro lines by block crossings
• Crossing Minimization in Storyline Visualization
• An improved algorithm for the metro-line crossing minimization problem
• Parameterized analysis and crossing minimization problems
• Two Polynomial Time Algorithms for the Metro-line Crossing Minimization Problem

This page was built for publication: Metro-line crossing minimization: hardness, approximations, and tractable cases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2867669)