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

DOI10.1007/978-3-319-03841-4_29zbMATH Open1406.68076arXiv1306.2079OpenAlexW8509995MaRDI QIDQ2867669FDOQ2867669

Authors: Martin Fink, Sergey Pupyrev 

Publication date: 20 December 2013

Published in: Graph Drawing (Search for Journal in Brave)

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.

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

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

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)

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)