Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102492
Title: Metro-line crossing minimization: Hardness, approximations, and tractable cases
Authors: Fink, M.
Pupyrev, S.
Issue Date: 2013
Publisher: Springer Verlag
Citation: Fink M. Metro-line crossing minimization: Hardness, approximations, and tractable cases / M. Fink, S. Pupyrev. — DOI 10.1007/978-3-319-03841-4_29 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2013. — Vol. 8242 LNCS. — P. 328-339.
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(√log |L|)-approximation algorithm for MLCM-P. © 2013 Springer International Publishing Switzerland.
Keywords: APPROXIMATION ALGORITHMS
DRAWING (GRAPHICS)
NP-HARD
CENTRAL PROBLEMS
CROSSING MINIMIZATION
EMBEDDED GRAPHS
GRAPH DRAWING
LINE ENDS
METRO LINES
GRAPH THEORY
URI: http://hdl.handle.net/10995/102492
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84891859685
PURE ID: 841916
ad295525-392a-43ac-bb83-439705232531
ISSN: 3029743
ISBN: 9783319038407
DOI: 10.1007/978-3-319-03841-4_29
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84891859685.pdf359,91 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.