{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:19:28Z","timestamp":1787390368902,"version":"build-2736575974"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,8]]},"abstract":"<jats:p>A new algorithm is given to find a maximum flow in an undirected planar flow network in $O(n\\log ^2 n)$ time, which is faster than the best method previously known by a factor of $\\sqrt n \/\\log n$. The algorithm constructs a transformation of the dual of the given flow network in which differences between shortest distances are equal, under suitable edge correspondences, to edge flows in the given network. The transformation depends on the value of a maximum flow. The algorithm then solves the shortest distances problem efficiently by exploiting certain structural properties of the transformed dual, as well as using a set of cuts constructible in $O(n\\log ^2 n)$ time by a known method which is also used to find the requisite flow value. The main result can be further improved by a factor of $\\log n\/\\log^* n$ if a recently developed shortest path algorithm for planar networks is used in place of Dijkstra\u2019s algorithm in each step where shortest paths are computed.<\/jats:p>","DOI":"10.1137\/0214045","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"612-624","source":"Crossref","is-referenced-by-count":42,"title":["An $O(n\\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks"],"prefix":"10.1137","volume":"14","author":[{"given":"Refael","family":"Hassin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Donald B.","family":"Johnson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,2]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"G. N. Frederickson,  Shortest path problems in planar graphs,  Proc. 24th Annual Symposium on Foundations of Computer Science,  1983,  242\u2013247","DOI":"10.1109\/SFCS.1983.69"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.5"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90120-4"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0208012"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321993"},{"key":"R8","unstructured":"D. B. Johnson, S. M. Venkatesan,  Using divide and conquer to find flows in directed planar networks in  $O(n^{3\/2}\\log n)$ time,  Proc. Twentieth Annual Allerton Conference on Communication, Control, and Computing, Univ. Illinois, Urbana,  1982,  898\u2013905, October"},{"key":"R9","volume-title":"Combinatorial optimization: networks and matroids","author":"Lawler Eugene L.","year":"1976"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0212005"},{"key":"R12","unstructured":"D. D. Sleator, Masters Thesis,  An  $O(nm\\log n)$ algorithm for maximum network flow, Ph.D. Dissertation, Comp. Sci. Dept., Stanford Univ., Stanford, CA,  1980"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:10Z","timestamp":1787337550000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,8]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1985,8]]}},"alternative-id":["10.1137\/0214045"],"URL":"https:\/\/doi.org\/10.1137\/0214045","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,8]]}}}