{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T15:18:21Z","timestamp":1725981501823},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319718392"},{"type":"electronic","value":"9783319718408"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-71840-8_5","type":"book-chapter","created":{"date-parts":[[2018,6,18]],"date-time":"2018-06-18T20:19:25Z","timestamp":1529353165000},"page":"207-243","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Planar Digraphs"],"prefix":"10.1007","author":[{"given":"Marcin","family":"Pilipczuk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,19]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1016\/j.jctb.2016.10.001","volume":"122","author":"I Adler","year":"2017","unstructured":"I.\u00a0Adler, S.G. Kolliopoulos, P.K. Krause, D.\u00a0Lokshtanov, S.\u00a0Saurabh, and D.\u00a0M. Thilikos. Irrelevant vertices for the planar Disjoint Paths problem. J. Combin. Theory Ser. B, 122:815\u2013843, 2017.","journal-title":"J. Combin. Theory Ser. B"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"G.\u00a0Borradaile and P.N. Klein. An $${O}(n \\log n)$$ algorithm for maximum $$st$$-flow in a directed planar graph. J. Assoc. Comput. Mach., 56(2), 2009.","DOI":"10.1145\/1502793.1502798"},{"issue":"1\u20132","key":"5_CR3","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s10107-014-0856-z","volume":"154","author":"C Chekuri","year":"2015","unstructured":"C.\u00a0Chekuri and A.\u00a0Ene. The all-or-nothing flow problem in directed graphs with symmetric demand pairs. Math. Program., 154(1-2):249\u2013272, 2015.","journal-title":"Math. Program."},{"key":"5_CR4","unstructured":"C.\u00a0Chekuri, A.\u00a0Ene, and M.\u00a0Pilipczuk. Constant congestion routing of symmetric demands in planar directed graphs. In I.\u00a0Chatzigiannakis, M.\u00a0Mitzenmacher, Y.\u00a0Rabani, and D.\u00a0Sangiorgi, editors, ICALP 2016: The 43rd International Colloquium on Automata, Languages, and Programming, volume\u00a055 of LIPIcs, pages 7:1\u20137:14, 2016."},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"C.\u00a0Chekuri, S.\u00a0Khanna, and F.B. Shepherd. Multicommodity flow, well-linked terminals, and routing problems. In H.\u00a0N. Gabow and R.\u00a0Fagin, editors, STOC 2005: 37th Annual ACM Symposium on Theory of Computing, pages 183\u2013192. ACM, 2005.","DOI":"10.1145\/1060590.1060618"},{"issue":"5","key":"5_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2893472","volume":"63","author":"Julia Chuzhoy","year":"2016","unstructured":"J.\u00a0Chuzhoy and S.\u00a0Li. A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. J. Assoc. Comput. Mach., 63(5):45:1\u201345:51, 2016.","journal-title":"Journal of the ACM"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"M.\u00a0Cygan, D.\u00a0Marx, M.\u00a0Pilipczuk, and M.\u00a0Pilipczuk. The planar directed $$k$$-Vertex-Disjoint Paths problem is fixed-parameter tractable. In FOCS 2013: 54th Annual IEEE Symposium on Foundations of Computer Science, pages 197\u2013206. IEEE Computer Society, 2013.","DOI":"10.1109\/FOCS.2013.29"},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1965-035-8","volume":"17","author":"P Erd\u0151s","year":"1965","unstructured":"P.\u00a0Erd\u0151s and L.\u00a0P\u00f3sa. On independent circuits contained in a graph. Canadian J. Math., 17:347\u2013352, 1965.","journal-title":"Canadian J. Math."},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1137\/1.9781611973075.65","volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Jeff Erickson","year":"2010","unstructured":"J.\u00a0Erickson. Maximum flows and parametric shortest paths in planar graphs. In M.\u00a0Charikar, editor, SODA 2010: 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 794\u2013804. SIAM, 2010."},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"F.V. Fomin, E.D. Demaine, M.\u00a0Hajiaghayi, and D.M. Thilikos. Bidimensionality. In Encyclopedia of Algorithms, pages 203\u2013207. Springer, 2016.","DOI":"10.1007\/978-1-4939-2864-4_47"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"S.\u00a0Fortune, J.E. Hopcroft, and J.\u00a0Wyllie. The directed subgraph homeomorphism problem. Theor. Comput. Sci., 10:111\u2013121, 1980.","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"5_CR12","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/s00453-012-9627-5","volume":"64","author":"Q-P Gu","year":"2012","unstructured":"Q.-P. Gu and H.\u00a0Tamaki. Improved bounds on the planar branchwidth with respect to the largest grid minor size. Algorithmica, 64(3):416\u2013453, 2012.","journal-title":"Algorithmica"},{"issue":"3","key":"5_CR13","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0020-0190(81)90120-4","volume":"13","author":"R Hassin","year":"1981","unstructured":"R.\u00a0Hassin. Maximum flow in $$(s, t)$$ planar networks. Inform. Process. Lett., 13(3):107, 1981.","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"5_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"MR Henzinger","year":"1997","unstructured":"M.R. Henzinger, P.N. Klein, S.\u00a0Rao, and S.\u00a0Subramanian. Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci., 55(1):3\u201323, 1997.","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"5_CR15","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T Johnson","year":"2001","unstructured":"T.\u00a0Johnson, N.\u00a0Robertson, P.D. Seymour, and R.\u00a0Thomas. Directed Tree-Width. J. Combin. Theory Ser. B, 82(1):138\u2013154, 2001.","journal-title":"J. Combin. Theory Ser. B"},{"key":"5_CR16","unstructured":"T.\u00a0Johnson, N.\u00a0Robertson, P.\u00a0D. Seymour, and R.\u00a0Thomas. Excluding a grid minor in planar digraphs. CoRR, arxiv.org\/abs\/1510.00473 , 2015."},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"K.\u00a0Kawarabayashi and S.\u00a0Kreutzer. The directed grid theorem. In STOC 2015: 47th Annual ACM on Symposium on Theory of Computing, pages 655\u2013664. ACM, 2015.","DOI":"10.1145\/2746539.2746586"},{"issue":"4","key":"5_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1538902.1538903","volume":"56","author":"Rohit Khandekar","year":"2009","unstructured":"R.\u00a0Khandekar, S.\u00a0Rao, and U.V. Vazirani. Graph partitioning using single commodity flows. J. ACM, 56(4), 2009.","journal-title":"Journal of the ACM"},{"key":"5_CR19","unstructured":"P.N. Klein and S.\u00a0Mozes. Optimization Algorithms for Planar Graphs. Available at http:\/\/planarity.org , 2016."},{"key":"5_CR20","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"D.\u00a0Lokshtanov, D.\u00a0Marx, and S.\u00a0Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS, 105:41\u201372, 2011.","journal-title":"Bulletin of the EATCS"},{"key":"5_CR21","unstructured":"A.\u00a0Louis. Cut-matching games on directed graphs. CoRR, arxiv.org\/abs\/1010.1047 , 2010."},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"B.\u00a0Mohar and C.\u00a0Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001.","DOI":"10.56021\/9780801866890"},{"issue":"4","key":"5_CR23","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/BF01271272","volume":"16","author":"B Reed","year":"1996","unstructured":"B.\u00a0Reed, N.\u00a0Robertson, P.D. Seymour, and R.\u00a0Thomas. Packing directed circuits. Combinatorica, 16(4):535\u2013554, 1996.","journal-title":"Combinatorica"},{"key":"5_CR24","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"The disjoint paths problem","year":"1995","unstructured":"N.\u00a0Robertson and P.D. Seymour. Graph minors. XIII: The disjoint paths problem. J. Combin. Theory Ser. B, 63:65\u2013110, 1995.","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"5_CR25","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N Robertson","year":"1994","unstructured":"N.\u00a0Robertson, P.D. Seymour, and R.\u00a0Thomas. Quickly excluding a planar graph. J. Combin. Theory Ser. B, 62(2):323\u2013348, 1994.","journal-title":"J. Combin. Theory Ser. B"},{"issue":"4","key":"5_CR26","doi-asserted-by":"publisher","first-page":"780","DOI":"10.1137\/S0097539792224061","volume":"23","author":"A Schrijver","year":"1994","unstructured":"A.\u00a0Schrijver. Finding $$k$$ disjoint paths in a directed planar graph. SIAM J. Comput., 23(4):780\u2013788, 1994.","journal-title":"SIAM J. Comput."},{"key":"5_CR27","unstructured":"A.\u00a0Schrijver. Free partially commutative groups, cohomology, and paths and circuits in directed graphs on surfaces. Preprint, available at http:\/\/homepages.cwi.nl\/lex\/files\/dppg.pdf ."},{"issue":"3","key":"5_CR28","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"D.D. Sleator and R.E. Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362\u2013391, 1983.","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR29","doi-asserted-by":"crossref","unstructured":"A.\u00a0Slivkins. Parameterized tractability of edge-disjoint paths on directed acyclic graphs. In ESA 2003: 11th Annual Eur. Symp. Algorithms, volume 2832 of Lect. Notes Comput. Sci., pages 482\u2013493, 2003.","DOI":"10.1007\/978-3-540-39658-1_44"},{"key":"5_CR30","unstructured":"D.H. Younger. Graphs with interlinked directed circuits,. In Midwest symposium on circuit theory 2, pages XVI 2.1\u2013XVI 2.7, 1973."}],"container-title":["Springer Monographs in Mathematics","Classes of Directed Graphs"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-71840-8_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,3]],"date-time":"2023-09-03T07:03:11Z","timestamp":1693724591000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-71840-8_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319718392","9783319718408"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-71840-8_5","relation":{},"ISSN":["1439-7382","2196-9922"],"issn-type":[{"type":"print","value":"1439-7382"},{"type":"electronic","value":"2196-9922"}],"subject":[],"published":{"date-parts":[[2018]]}}}