{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:30:11Z","timestamp":1725795011420},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319066851"},{"type":"electronic","value":"9783319066868"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-06686-8_5","type":"book-chapter","created":{"date-parts":[[2014,6,2]],"date-time":"2014-06-02T05:30:40Z","timestamp":1401687040000},"page":"52-64","source":"Crossref","is-referenced-by-count":2,"title":["Vertex Disjoint Paths in Upward Planar Graphs"],"prefix":"10.1007","author":[{"given":"Saeed","family":"Akhoondian Amiri","sequence":"first","affiliation":[]},{"given":"Ali","family":"Golshani","sequence":"additional","affiliation":[]},{"given":"Stephan","family":"Kreutzer","sequence":"additional","affiliation":[]},{"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., Gutin, G.Z.: Digraphs - Theory, Algorithms and Applications, 2nd edn. Springer (2010)","DOI":"10.1007\/978-1-84800-998-1"},{"key":"5_CR2","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"G.D. Battista","year":"1999","unstructured":"Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1999)"},{"issue":"6","key":"5_CR3","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/BF01188716","volume":"12","author":"P. Bertolazzi","year":"1994","unstructured":"Bertolazzi, P., Di Battista, G., Liotta, G., Mannino, C.: Upward drawings of triconnected digraphs. Algorithmica\u00a012(6), 476\u2013497 (1994)","journal-title":"Algorithmica"},{"issue":"1","key":"5_CR4","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1137\/S0097539794279626","volume":"27","author":"P. Bertolazzi","year":"1998","unstructured":"Bertolazzi, P., Di Battista, G., Mannino, C., Tamassia, R.: Optimal upward planarity testing of single-source digraphs. SIAM J. Comput.\u00a027(1), 132\u2013169 (1998)","journal-title":"SIAM J. Comput."},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"Cygan, M., Marx, D., Pilipczuk, M., Pilipczuk, M.: The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 197\u2013206 (2013)","DOI":"10.1109\/FOCS.2013.29"},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer (2005)","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer (1998)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J.E., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci.\u00a010, 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"5_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-642-11269-0_15","volume-title":"Parameterized and Exact Computation","author":"R. Ganian","year":"2009","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Kneis, J., Langer, A., Obdr\u017e\u00e1lek, J., Rossmanith, P.: On digraph width measures in parameterized algorithmics. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 185\u2013197. Springer, Heidelberg (2009)"},{"key":"5_CR10","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman (1979)"},{"issue":"2","key":"5_CR11","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1137\/S0097539794277123","volume":"31","author":"A. Garg","year":"2001","unstructured":"Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput.\u00a031(2), 601\u2013625 (2001)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"5_CR12","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T. Johnson","year":"2001","unstructured":"Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. J. Comb. Theory, Ser. B\u00a082(1), 138\u2013154 (2001)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"3","key":"5_CR13","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1061425.1061430","volume":"5","author":"J.F. Lynch","year":"1975","unstructured":"Lynch, J.F.: The equivalence of theorem proving and the interconnection problem. ACM SIGDA Newsletter\u00a05(3), 31\u201336 (1975)","journal-title":"ACM SIGDA Newsletter"},{"key":"5_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/3-540-10704-5_18","volume-title":"Graph Theory and Algorithms","author":"T. Ohtsuki","year":"1981","unstructured":"Ohtsuki, T.: The two disjoint path problem and wire routing design. In: Saito, N., Nishizeki, T. (eds.) Graph Theory and Algorithms. LNCS, vol.\u00a0108, pp. 207\u2013216. Springer, Heidelberg (1981)"},{"key":"5_CR15","unstructured":"Papakostas, A.: Upward planarity testing of outerplanar dags (extended abstract) (1995), 10.1007\/3-540-58950-3_385"},{"key":"5_CR16","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. Journal of Combinatorial Theory, Series B\u00a063, 65\u2013110 (1995)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"4","key":"5_CR17","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 Jornal on Computing\u00a023(4), 780\u2013788 (1994)","journal-title":"SIAM Jornal on Computing"},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0012-365X(80)90158-2","volume":"29","author":"P.D. Seymour","year":"1980","unstructured":"Seymour, P.D.: Disjoint paths in graphs. Discrete Math.\u00a029, 293\u2013309 (1980)","journal-title":"Discrete Math."},{"key":"5_CR19","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1145\/322203.322207","volume":"27","author":"Y. Shiloach","year":"1980","unstructured":"Shiloach, Y.: A polynomial solution to the undirected two paths problem. J. ACM\u00a027, 445\u2013456 (1980)","journal-title":"J. ACM"},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"Slivkins, A.: Parameterized tractability of edge-disjoint paths on directed acyclic graphs. In: European Symposium on Algorithms, pp. 482\u2013493 (2003)","DOI":"10.1007\/978-3-540-39658-1_44"},{"key":"5_CR21","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/S0195-6698(80)80039-4","volume":"1","author":"C. Thomassen","year":"1980","unstructured":"Thomassen, C.: 2-linked graphs. European Journal of Combinatorics\u00a01, 371\u2013378 (1980)","journal-title":"European Journal of Combinatorics"}],"container-title":["Lecture Notes in Computer Science","Computer Science - Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-06686-8_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T23:54:02Z","timestamp":1558914842000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-06686-8_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319066851","9783319066868"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-06686-8_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}