{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T21:51:19Z","timestamp":1780523479026,"version":"3.54.1"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319038407","type":"print"},{"value":"9783319038414","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03841-4_29","type":"book-chapter","created":{"date-parts":[[2013,12,2]],"date-time":"2013-12-02T05:28:55Z","timestamp":1385962135000},"page":"328-339","source":"Crossref","is-referenced-by-count":9,"title":["Metro-Line Crossing Minimization: Hardness, Approximations, and Tractable Cases"],"prefix":"10.1007","author":[{"given":"Martin","family":"Fink","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sergey","family":"Pupyrev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"29_CR1","first-page":"573","volume-title":"STOC 2005","author":"A. Agarwal","year":"2005","unstructured":"Agarwal, A., Charikar, M., Makarychev, K., Makarychev, Y.: \n                    \n                      \n                    \n                    $O(\\sqrt{\\log n})$\n                   approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. In: STOC 2005, pp. 573\u2013581. ACM, New York (2005)"},{"issue":"1","key":"29_CR2","doi-asserted-by":"publisher","first-page":"75","DOI":"10.7155\/jgaa.00199","volume":"14","author":"E.N. Argyriou","year":"2010","unstructured":"Argyriou, E.N., Bekos, M.A., Kaufmann, M., Symvonis, A.: On metro-line crossing minimization. Journal of Graph Algorithms and Applications\u00a014(1), 75\u201396 (2010)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"29_CR3","unstructured":"Asquith, M., Gudmundsson, J., Merrick, D.: An ILP for the metro-line crossing problem. In: Harland, J., Manyem, P. (eds.) CATS 2008. CRPIT, vol.\u00a077, pp. 49\u201356. Australian Computer Society (2008)"},{"key":"29_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-540-77537-9_24","volume-title":"Graph Drawing","author":"M.A. Bekos","year":"2008","unstructured":"Bekos, M.A., Kaufmann, M., Potika, K., Symvonis, A.: Line crossing minimization on metro maps. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol.\u00a04875, pp. 231\u2013242. Springer, Heidelberg (2008)"},{"key":"29_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/978-3-540-70904-6_27","volume-title":"Graph Drawing","author":"M. Benkert","year":"2007","unstructured":"Benkert, M., N\u00f6llenburg, M., Uno, T., Wolff, A.: Minimizing intra-edge crossings in wiring diagrams and public transportation maps. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol.\u00a04372, pp. 270\u2013281. Springer, Heidelberg (2007)"},{"key":"29_CR6","unstructured":"Fink, M., Pupyrev, S.: Metro-line crossing minimization: Hardness, approximations, and tractable cases. ArXiv e-print abs\/1306.2079 (2013), \n                    \n                      http:\/\/arxiv.org\/abs\/1306.2079"},{"key":"29_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/978-3-642-40313-2_36","volume-title":"Mathematical Foundations of Computer Science 2013","author":"M. Fink","year":"2013","unstructured":"Fink, M., Pupyrev, S.: Ordering metro lines by block crossings. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol.\u00a08087, pp. 397\u2013408. Springer, Heidelberg (2013)"},{"issue":"6","key":"29_CR8","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1109\/54.41670","volume":"6","author":"P. Groeneveld","year":"1989","unstructured":"Groeneveld, P.: Wire ordering for detailed routing. IEEE Des. Test\u00a06(6), 6\u201317 (1989)","journal-title":"IEEE Des. Test"},{"issue":"1","key":"29_CR9","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0167-6377(81)90020-1","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Pulleyblank, W.: Weakly bipartite graphs and the Max-Cut problem. Operations Research Letters\u00a01(1), 23\u201327 (1981)","journal-title":"Operations Research Letters"},{"issue":"4","key":"29_CR10","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1109\/43.372368","volume":"14","author":"M. Marek-Sadowska","year":"1995","unstructured":"Marek-Sadowska, M., Sarrafzadeh, M.: The crossing distribution problem. IEEE Transactions on CAD of Integrated Circuits and Systems\u00a014(4), 423\u2013433 (1995)","journal-title":"IEEE Transactions on CAD of Integrated Circuits and Systems"},{"key":"29_CR11","unstructured":"N\u00f6llenburg, M.: Network Visualization: Algorithms, Applications, and Complexity. Ph.D. thesis, Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Karlsruhe (TH) (2009)"},{"key":"29_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/978-3-642-11805-0_36","volume-title":"Graph Drawing","author":"M. N\u00f6llenburg","year":"2010","unstructured":"N\u00f6llenburg, M.: An improved algorithm for the metro-line crossing minimization problem. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol.\u00a05849, pp. 381\u2013392. Springer, Heidelberg (2010)"},{"key":"29_CR13","unstructured":"Okamoto, Y., Tatsu, Y., Uno, Y.: Exact and fixed-parameter algorithms for metro-line crossing minimization problems. ArXiv e-print abs\/1306.3538 (2013)"},{"key":"29_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1007\/978-3-642-25878-7_14","volume-title":"GD 2011","author":"S. Pupyrev","year":"2012","unstructured":"Pupyrev, S., Nachmanson, L., Bereg, S., Holroyd, A.E.: Edge routing with ordered bundles. In: van Kreveld, M.J., Speckmann, B. (eds.) GD 2011. LNCS, vol.\u00a07034, pp. 136\u2013147. Springer, Heidelberg (2012)"},{"issue":"8","key":"29_CR15","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.jcss.2009.04.002","volume":"75","author":"I. Razgon","year":"2009","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-SAT is fixed-parameter tractable. Journal of Computer and System Sciences\u00a075(8), 435\u2013450 (2009)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-03841-4_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T01:29:46Z","timestamp":1558747786000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03841-4_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319038407","9783319038414"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03841-4_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}