{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T09:41:07Z","timestamp":1768729267333,"version":"3.49.0"},"publisher-location":"Cham","reference-count":61,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030420703","type":"print"},{"value":"9783030420710","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-42071-0_9","type":"book-chapter","created":{"date-parts":[[2020,4,22]],"date-time":"2020-04-22T17:02:44Z","timestamp":1587574964000},"page":"112-128","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,20]]},"reference":[{"key":"9_CR1","unstructured":"Adler, I.: List of open problems. In: 6th Workshop on Graph Classes, Optimization, and Width Parameters (2013). http:\/\/www.cs.upc.edu\/~sedthilk\/grow\/Open_Problems_GROW_2013.pdf"},{"issue":"50","key":"9_CR2","doi-asserted-by":"publisher","first-page":"7018","DOI":"10.1016\/j.tcs.2011.09.015","volume":"412","author":"I Adler","year":"2011","unstructured":"Adler, I., Dorn, F., Fomin, F.V., Sau, I., Thilikos, D.M.: Faster parameterized algorithms for minor containment. Theor. Comput. Sci. 412(50), 7018\u20137028 (2011). https:\/\/doi.org\/10.1016\/j.tcs.2011.09.015","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9_CR3","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s00453-011-9563-9","volume":"64","author":"I Adler","year":"2012","unstructured":"Adler, I., Dorn, F., Fomin, F.V., Sau, I., Thilikos, D.M.: Fast minor testing in planar graphs. Algorithmica 64(1), 69\u201384 (2012). https:\/\/doi.org\/10.1007\/s00453-011-9563-9","journal-title":"Algorithmica"},{"key":"9_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/978-3-642-22006-7_10","volume-title":"Automata, Languages and Programming","author":"I Adler","year":"2011","unstructured":"Adler, I., Kolliopoulos, S.G., Krause, P.K., Lokshtanov, D., Saurabh, S., Thilikos, D.: Tight bounds for linkages in planar graphs. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6755, pp. 110\u2013121. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22006-7_10"},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1016\/j.jctb.2016.10.001","volume":"122","author":"I Adler","year":"2017","unstructured":"Adler, I., Kolliopoulos, S.G., Krause, P.K., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Irrelevant vertices for the planar disjoint paths problem. J. Comb. Theory Ser. B 122, 815\u2013843 (2017). https:\/\/doi.org\/10.1016\/j.jctb.2016.10.001","journal-title":"J. Comb. Theory Ser. B"},{"key":"9_CR6","unstructured":"Adler, I., Krause, P.K.: A lower bound for the tree-width of planar graphs with vital linkages. CoRR abs\/1011.2136 (2010). http:\/\/arxiv.org\/abs\/1011.2136"},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2014.12.010","volume":"570","author":"J Baste","year":"2015","unstructured":"Baste, J., Sau, I.: The role of planarity in connectivity problems parameterized by treewidth. Theor. Comput. Sci. 570, 1\u201314 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2014.12.010","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"9_CR8","doi-asserted-by":"publisher","first-page":"44:1","DOI":"10.1145\/2973749","volume":"63","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. J. ACM 63(5), 44:1\u201344:69 (2016). https:\/\/doi.org\/10.1145\/2973749","journal-title":"J. ACM"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Chuzhoy, J.: Polynomial bounds for the grid-minor theorem. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, 31 May\u201303 June 2014, pp. 60\u201369 (2014)","DOI":"10.1145\/2591796.2591813"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J.: Improved bounds for the flat wall theorem. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, pp. 256\u2013275 (2015)","DOI":"10.1137\/1.9781611973730.20"},{"key":"9_CR11","unstructured":"Chuzhoy, J., Kim, D.H.K.: On approximating node-disjoint paths in grids. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2015, Princeton, NJ, USA, 24\u201326 August 2015. LIPIcs, vol. 40, pp. 187\u2013211. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)"},{"key":"9_CR12","unstructured":"Chuzhoy, J., Kim, D.H.K., Li, S.: Improved approximation for node-disjoint paths in planar graphs. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, 18\u201321 June 2016, pp. 556\u2013569. ACM (2016)"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Kim, D.H.K., Nimavat, R.: New hardness results for routing on disjoint paths. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, 19\u201323 June 2017, pp. 86\u201399. ACM (2017)","DOI":"10.1145\/3055399.3055411"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Kim, D.H.K., Nimavat, R.: Almost polynomial hardness of node-disjoint paths in grids. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, 25\u201329 June 2018, pp. 1220\u20131233. ACM (2018)","DOI":"10.1145\/3188745.3188772"},{"key":"9_CR15","unstructured":"Chuzhoy, J., Kim, D.H.K., Nimavat, R.: Improved approximation for node-disjoint paths in grids with sources on the boundary. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, 9\u201313 July 2018. LIPIcs, vol. 107, pp. 38:1\u201338:14 (2018)"},{"key":"9_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"9_CR17","doi-asserted-by":"publisher","unstructured":"Cygan, M., Marx, D., Pilipczuk, M., Pilipczuk, M.: The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, Berkeley, CA, USA, 26\u201329 October 2013, pp. 197\u2013206 (2013). https:\/\/doi.org\/10.1109\/FOCS.2013.29","DOI":"10.1109\/FOCS.2013.29"},{"issue":"1","key":"9_CR18","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/1077464.1077468","volume":"1","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Fixed-parameter algorithms for ($$k$$, $$r$$)-center in planar graphs and map graphs. ACM Trans. Algorithms 1(1), 33\u201347 (2005)","journal-title":"ACM Trans. Algorithms"},{"issue":"6","key":"9_CR19","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and $${H}$$-minor-free graphs. J. ACM 52(6), 866\u2013893 (2005)","journal-title":"J. ACM"},{"key":"9_CR20","unstructured":"Demaine, E.D., Hajiaghayi, M.T.: Bidimensionality: new connections between FPT algorithms and PTASs. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Canada, pp. 590\u2013601 (2005)"},{"key":"9_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-642-30891-8_2","volume-title":"The Multivariate Algorithmic Revolution and Beyond","author":"R Downey","year":"2012","unstructured":"Downey, R.: The birth and early years of parameterized complexity. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) The Multivariate Algorithmic Revolution and Beyond. LNCS, vol. 7370, pp. 17\u201338. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-30891-8_2"},{"key":"9_CR22","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter intractability. In: Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, Massachusetts, USA, 22\u201325 June 1992, pp. 36\u201349 (1992). https:\/\/doi.org\/10.1109\/SCT.1992.215379","DOI":"10.1109\/SCT.1992.215379"},{"key":"9_CR23","unstructured":"Dvorak, Z., Kr\u00e1l, D., Thomas, R.: Coloring triangle-free graphs on surfaces. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, 4\u20136 January 2009, pp. 120\u2013129 (2009). http:\/\/dl.acm.org\/citation.cfm?id=1496770.1496784"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"Fellows, M.R.: The Robertson-Seymour theorems: a survey of applications. In: Graphs and Algorithms: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference Held 28 June\u20134 July 1987 with Support from the National Science Foundation, pp. 1\u201318 (1989)","DOI":"10.1090\/conm\/089\/1006472"},{"issue":"3","key":"9_CR25","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1016\/j.jcss.2011.10.003","volume":"78","author":"MR Fellows","year":"2012","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F.A., Saurabh, S., Villanger, Y.: Local search: is brute-force avoidable? J. Comput. Syst. Sci. 78(3), 707\u2013719 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR26","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Bidimensionality and EPTAS. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, USA, pp. 748\u2013759 (2011)","DOI":"10.1137\/1.9781611973082.59"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S.: Bidimensionality and geometric graphs. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 17\u201319 January 2012, pp. 1563\u20131575 (2012)","DOI":"10.1137\/1.9781611973099.124"},{"key":"9_CR28","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, USA, pp. 503\u2013510 (2010)","DOI":"10.1137\/1.9781611973075.43"},{"key":"9_CR29","unstructured":"Frank, A.: Packing paths, cuts, and circuits-a survey. Paths, Flows and VLSI-Layout, pp. 49\u2013100 (1990)"},{"key":"9_CR30","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"9_CR31","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.jctb.2018.03.004","volume":"132","author":"J Geelen","year":"2018","unstructured":"Geelen, J., Huynh, T., Richter, R.B.: Explicit bounds for graph minors. J. Comb. Theory Ser. B 132, 80\u2013106 (2018). https:\/\/doi.org\/10.1016\/j.jctb.2018.03.004","journal-title":"J. Comb. Theory Ser. B"},{"key":"9_CR32","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.tcs.2012.12.041","volume":"476","author":"PA Golovach","year":"2013","unstructured":"Golovach, P.A., van\u2019t Hof, P.: Obtaining planarity bycontracting few edges. Theor. Comput. Sci. 476, 38\u201346 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2012.12.041","journal-title":"Theor. Comput. Sci."},{"key":"9_CR33","doi-asserted-by":"publisher","unstructured":"Grohe, M., Kawarabayashi, K., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6\u20138 June 2011, pp. 479\u2013488 (2011). https:\/\/doi.org\/10.1145\/1993636.1993700","DOI":"10.1145\/1993636.1993700"},{"key":"9_CR34","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kawarabayashi, K., Reed, B.A.: A simple algorithm for the graph minor decomposition - logic meets structural graph theory. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, pp. 414\u2013431 (2013)","DOI":"10.1137\/1.9781611973105.30"},{"issue":"2","key":"9_CR35","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0196-6774(87)90043-5","volume":"8","author":"DS Johnson","year":"1987","unstructured":"Johnson, D.S.: The NP-completeness column: an ongoing guide. J. Algorithms 8(2), 285\u2013303 (1987). https:\/\/doi.org\/10.1016\/0196-6774(87)90043-5","journal-title":"J. Algorithms"},{"issue":"1","key":"9_CR36","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"RM Karp","year":"1975","unstructured":"Karp, R.M.: On the computational complexity of combinatorial problems. Networks 5(1), 45\u201368 (1975). https:\/\/doi.org\/10.1002\/net.1975.5.1.45","journal-title":"Networks"},{"issue":"2","key":"9_CR37","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/j.jctb.2011.07.004","volume":"102","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y., Reed, B.A.: The disjoint paths problem in quadratic time. J. Comb. Theory Ser. B 102(2), 424\u2013435 (2012). https:\/\/doi.org\/10.1016\/j.jctb.2011.07.004","journal-title":"J. Comb. Theory Ser. B"},{"key":"9_CR38","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Wollan, P.: A shorter proof of the graph minor algorithm: the unique linkage theorem. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5\u20138 June 2010, pp. 687\u2013694 (2010)","DOI":"10.1145\/1806689.1806784"},{"key":"9_CR39","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Wollan, P.: A simpler algorithm and shorter proof for the graph minor decomposition. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6\u20138 June 2011, pp. 451\u2013458 (2011)","DOI":"10.1145\/1993636.1993697"},{"key":"9_CR40","unstructured":"Kobayashi, Y., Kawarabayashi, K.: Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, 4\u20136 January 2009, pp. 1146\u20131155 (2009). http:\/\/dl.acm.org\/citation.cfm?id=1496770.1496894"},{"key":"9_CR41","first-page":"129","volume":"2","author":"MR Kramer","year":"1984","unstructured":"Kramer, M.R., van Leeuwen, J.: The complexity of wirerouting and finding minimum area layouts for arbitrary VLSI circuits. Adv. Comput. Res. 2, 129\u2013146 (1984)","journal-title":"Adv. Comput. Res."},{"key":"9_CR42","doi-asserted-by":"publisher","first-page":"271","DOI":"10.4064\/fm-15-1-271-283","volume":"15","author":"K Kuratowski","year":"1930","unstructured":"Kuratowski, K.: Sur le probl\u00e8me des courbes gauches en topologie. Fund. Math. 15, 271\u2013283 (1930). (in French)","journal-title":"Fund. Math."},{"key":"9_CR43","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41422-0","volume-title":"People, Problems, and Proofs: Essays from G\u00f6del\u2019s Lost Letter: 2010","author":"RJ Lipton","year":"2013","unstructured":"Lipton, R.J., Regan, K.W.: People, Problems, and Proofs: Essays from G\u00f6del\u2019s Lost Letter: 2010. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-41422-0"},{"issue":"3","key":"9_CR44","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/16M1104834","volume":"47","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. SIAM J. Comput. 47(3), 675\u2013702 (2018). https:\/\/doi.org\/10.1137\/16M1104834","journal-title":"SIAM J. Comput."},{"key":"9_CR45","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Misra, P., Pilipczuk, M., Saurabh, S., Zehavi, M.: An exponential time parameterized algorithm for planar disjoint paths. Manuscript in Preparation (2019)","DOI":"10.1145\/3357713.3384250"},{"key":"9_CR46","unstructured":"Lokshtanov, D., Saurabh, S., Wahlstr\u00f6m, M.: Subexponential parameterized odd cycle transversal on planar graphs. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, India, pp. 424\u2013434 (2012)"},{"issue":"3","key":"9_CR47","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1061425.1061430","volume":"5","author":"JF Lynch","year":"1975","unstructured":"Lynch, J.F.: The equivalence of theorem proving and the interconnection problem. ACM SIGDA Newslett. 5(3), 31\u201336 (1975)","journal-title":"ACM SIGDA Newslett."},{"issue":"4","key":"9_CR48","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/s00453-008-9233-8","volume":"57","author":"D Marx","year":"2010","unstructured":"Marx, D.: Chordal deletion is fixed-parameter tractable. Algorithmica 57(4), 747\u2013768 (2010). https:\/\/doi.org\/10.1007\/s00453-008-9233-8","journal-title":"Algorithmica"},{"key":"9_CR49","unstructured":"Mazoit, F.: A single exponential bound for the redundant vertex theorem on surfaces. arXiv preprint arXiv:1309.7820 (2013)"},{"issue":"2","key":"9_CR50","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1109\/18.212275","volume":"39","author":"RG Ogier","year":"1993","unstructured":"Ogier, R.G., Rutenburg, V., Shacham, N.: Distributed algorithms for computing shortest pairs of disjoint paths. IEEE Trans. Inf. Theory 39(2), 443\u2013455 (1993). https:\/\/doi.org\/10.1109\/18.212275","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9_CR51","doi-asserted-by":"crossref","unstructured":"Pilipczuk, M., Pilipczuk, M., Sankowski, P., van Leeuwen, E.J.: Network sparsification for Steiner problems on planar and bounded-genus graphs. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, USA, pp. 276\u2013285 (2014)","DOI":"10.1109\/FOCS.2014.37"},{"issue":"2\u20133","key":"9_CR52","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/0166-218X(94)00104-L","volume":"57","author":"BA Reed","year":"1995","unstructured":"Reed, B.A.: Rooted routing in the plane. Discrete Appl. Math. 57(2\u20133), 213\u2013227 (1995). https:\/\/doi.org\/10.1016\/0166-218X(94)00104-L","journal-title":"Discrete Appl. Math."},{"key":"9_CR53","doi-asserted-by":"crossref","unstructured":"Reed, B.A., Robertson, N., Schrijver, A., Seymour, P.D.: Finding disjoint trees in planar graphs in linear time. In: Graph Structure Theory, Proceedings of a AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors held June 22 to July 5, 1991, at the University of Washington, Seattle, USA, pp. 295\u2013301 (1991)","DOI":"10.21236\/ADA266435"},{"issue":"1","key":"9_CR54","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Ser. B 63(1), 65\u2013110 (1995). https:\/\/doi.org\/10.1006\/jctb.1995.1006","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"9_CR55","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1016\/j.jctb.2007.12.007","volume":"102","author":"N Robertson","year":"2012","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XXII. Irrelevant vertices in linkage problems. J. Comb. Theory Ser. B 102(2), 530\u2013563 (2012). https:\/\/doi.org\/10.1016\/j.jctb.2007.12.007","journal-title":"J. Comb. Theory Ser. B"},{"key":"9_CR56","unstructured":"Scheffler, P.: A practical linear time algorithm for disjoint paths in graphs with bounded tree-width. TU, Fachbereich 3 (1994)"},{"issue":"4","key":"9_CR57","doi-asserted-by":"publisher","first-page":"780","DOI":"10.1137\/S0097539792224061","volume":"23","author":"A Schrijver","year":"1994","unstructured":"Schrijver, A.: Finding k disjoint paths in a directed planar graph. SIAM J. Comput. 23(4), 780\u2013788 (1994). https:\/\/doi.org\/10.1137\/S0097539792224061","journal-title":"SIAM J. Comput."},{"key":"9_CR58","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer, Heidelberg (2003)"},{"issue":"4","key":"9_CR59","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s11276-005-1765-0","volume":"11","author":"A Srinivas","year":"2005","unstructured":"Srinivas, A., Modiano, E.: Finding minimum energy disjoint paths in wireless ad-hoc networks. Wirel. Netw. 11(4), 401\u2013417 (2005). https:\/\/doi.org\/10.1007\/s11276-005-1765-0","journal-title":"Wirel. Netw."},{"issue":"1","key":"9_CR60","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1007\/BF01594196","volume":"114","author":"K Wagner","year":"1937","unstructured":"Wagner, K.: \u00dcber eine eigenschaft der ebenen komplexe. Math. Ann 114(1), 570\u2013590 (1937)","journal-title":"Math. Ann"},{"key":"9_CR61","unstructured":"Wollan, P.: Personal communication, January 2015"}],"container-title":["Lecture Notes in Computer Science","Treewidth, Kernels, and Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-42071-0_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,18]],"date-time":"2022-12-18T14:03:27Z","timestamp":1671372207000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-42071-0_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030420703","9783030420710"],"references-count":61,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-42071-0_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"20 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}