@inproceedings{fp-mlcmhatc-GD13,
  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(\sqrt{\log |L|})$-approximation algorithm for MLCM-P.},
  added-at = {2013-08-08T10:47:28.000+0200},
  author = {Fink, Martin and Pupyrev, Sergey},
  biburl = {https://www.bibsonomy.org/bibtex/2c9107ab70ebc8fd6afd09264885736dd/fink},
  booktitle = {Proc. 21st Int. Sympos. Graph Drawing (GD'13)},
  editor = {Wismath, Stephen and Wolff, Alexander},
  interhash = {e8e9b7d0ff3c8d3695904d2642b72523},
  intrahash = {c9107ab70ebc8fd6afd09264885736dd},
  keywords = {approximation crossing hardness line metro minimization myown},
  pages = {328--339},
  pdf = {http://www1.informatik.uni-wuerzburg.de/pub/fink/paper/fp-mlcmhatc-GD13.pdf},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  slides = {http://www1.informatik.uni-wuerzburg.de/pub/fink/slides/fp-mlcmhatc-GD13-slides.pdf},
  timestamp = {2013-12-03T17:52:26.000+0100},
  title = {Metro-Line Crossing Minimization: Hardness, Approximations, and Tractable Cases},
  url = {http://dx.doi.org/10.1007/978-3-319-03841-4_29},
  volume = 8242,
  year = 2013
}