[1]   Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein: Inapproximabilty of densest k-subgraph from average case hardness, 2011. Manuscript.

[2]    Noga Alon, Paul Seymour, and Robin Thomas: Planar separators. SIAM J. Discr. Math., 7(2):184–193, 1994. [doi:10.1137/S0895480191198768]

[3]   Matthew Andrews: Approximation algorithms for the edge-disjoint paths problem via Raecke decompositions. In Proc. 51st FOCS, pp. 277–286. IEEE Comp. Soc., 2010. [doi:10.1109/FOCS.2010.33]

[4]   Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, and Lisa Zhang: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica, 30(5):485–520, 2010. [doi:10.1007/s00493-010-2455-9]

[5]   Matthew Andrews and Lisa Zhang: Logarithmic hardness of the undirected edge-disjoint paths problem. J. ACM, 53(5):745–761, 2006. [doi:10.1145/1183907.1183910]

[6]   Yonatan Aumann and Yuval Rabani: Improved bounds for all optical routing. In Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’95), pp. 567–576. SIAM, 1995. ACM DL.

[7]   Baruch Awerbuch, Rainer Gawlick, Tom Leighton, and Yuval Rabani: On-line admission control and circuit routing for high performance computing and communication. In Proc. 35th FOCS, pp. 412–423. IEEE Comp. Soc., 1994. [doi:10.1109/SFCS.1994.365675]

[8]   Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan: Detecting high log-densities: an O(n^1∕4) approximation for densest k-subgraph. In Proc. 42nd STOC, pp. 201–210. ACM Press, 2010. [doi:10.1145/1806689.1806719]

[9]   Andrei Z. Broder, Alan M. Frieze, Stephen Suen, and Eli Upfal: Optimal construction of edge-disjoint paths in random graphs. SIAM J. Comput., 28(2):541–573, 1998. [doi:10.1137/S0097539795290805]

[10]   Andrei Z. Broder, Alan M. Frieze, and Eli Upfal: Existence and construction of edge disjoint paths on expander graphs. SIAM J. Comput., 23(5):976–989, 1994. Preliminary version in STOC’92. [doi:10.1137/S0097539792232021]

[11]   Chandra Chekuri and Alina Ene: Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’13), pp. 326–341. SIAM, 2013. [doi:10.1137/1.9781611973105.24]

[12]   Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd: Multicommodity flow, well-linked terminals, and routing problems. In Proc. 37th STOC, pp. 183–192. ACM Press, 2005. [doi:10.1145/1060590.1060618]

[13]   Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd: An O() approximation and integrality gap for disjoint paths and unsplittable flow. Theory of Computing, 2(7):137–146, 2006. [doi:10.4086/toc.2006.v002a007]

[14]   Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd: Edge-disjoint paths in planar graphs with constant congestion. SIAM J. Comput., 39(1):281–301, 2009. Preliminary version in STOC’06. [doi:10.1137/060674442]

[15]   Chandra Chekuri, Marcelo Mydlarz, and F. Bruce Shepherd: Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms, 3(3):27:1–27:23, 2007. [doi:10.1145/1273340.1273343]

[16]   Julia Chuzhoy: Routing in undirected graphs with constant congestion. SIAM J. Comput., 45(4):1490–1532, 2016. [doi:10.1137/130910464]

[17]   Julia Chuzhoy and David Hong Kyun Kim: On approximating node-disjoint paths in grids. In Proc. 18th Internat. Workshop on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’15), pp. 187–211. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.APPROX-RANDOM.2015.187]

[18]   Julia Chuzhoy, David Hong Kyun Kim, and Shi Li: Improved approximation for node-disjoint paths in planar graphs. In Proc. 48th STOC, pp. 556–569. ACM Press, 2016. [doi:10.1145/2897518.2897538]

[19]   Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat: New hardness results for routing on disjoint paths. In Proc. 49th STOC, pp. 86–99. ACM Press, 2017. [doi:10.1145/3055399.3055411]

[20]   Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat: Almost polynomial hardness of node-disjoint paths in grids. In Proc. 50th STOC, pp. 1220–1233. ACM Press, 2018. [doi:10.1145/3188745.3188772]

[21]   Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat: Improved approximation for node-disjoint paths in grids with sources on the boundary. In Proc. 45th Internat. Colloq. on Automata, Languages, and Programming (ICALP’18), pp. 38:1–38:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ICALP.2018.38]

[22]   Julia Chuzhoy and Shi Li: A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. J. ACM, 63(5):45:1–45:51, 2016. Preliminary version in FOCS’12. [doi:10.1145/2893472]

[23]   Shimon Even, Alon Itai, and Adi Shamir: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput., 5(4):691–703, 1976. [doi:10.1137/0205048]

[24]   Uriel Feige: Relations between average case complexity and approximation complexity. In Proc. 34th STOC, pp. 534–543. ACM Press, 2002. [doi:10.1145/509907.509985]

[25]   Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz, and Aravind Srinivasan: Approximating the domatic number. SIAM J. Comput., 32(1):172–195, 2002. [doi:10.1137/S0097539700380754]

[26]   Krzysztof Fleszar, Matthias Mnich, and Joachim Spoerhase: New algorithms for maximum disjoint paths based on tree-likeness. Math. Programming, 171:433–461, 2018. Preliminary version in ESA’16. [doi:10.1007/s10107-017-1199-3]

[27]   Alan M. Frieze: Edge-disjoint paths in expander graphs. SIAM J. Comput., 30(6):1790–1801, 2001. Preliminary version in SODA’00. [doi:10.1137/S0097539700366103]

[28]   Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3–20, 1997. [doi:10.1007/BF02523685]

[29]   Thomas Holenstein: Parallel repetition: Simplification and the no-signaling case. Theory of Computing, 5(8):141–172, 2009. Preliminary version in STOC’07. [doi:10.4086/toc.2009.v005a008]

[30]   Richard Karp: On the complexity of combinatorial problems. Networks, 5(1):45–68, 1975. [doi:10.1002/net.1975.5.1.45]

[31]   Ken-Ichi Kawarabayashi and Yusuke Kobayashi: An O(log n)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs. ACM Trans. Algorithms, 9(2):16:1–16:13, 2013. [doi:10.1145/2438645.2438648]

[32]   Subhash Khot: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput., 36(4):1025–1071, 2006. [doi:10.1137/S0097539705447037]

[33]   Jon Kleinberg: An approximation algorithm for the disjoint paths problem in even-degree planar graphs. In Proc. 46th FOCS, pp. 627–636. IEEE Comp. Soc., 2005. [doi:10.1109/SFCS.2005.18]

[34]   Jon Kleinberg and Ronitt Rubinfeld: Short paths in expander graphs. In Proc. 37th FOCS, pp. 86–95. IEEE Comp. Soc., 1996. [doi:10.1109/SFCS.1996.548467]

[35]   Jon M. Kleinberg and Éva Tardos: Disjoint paths in densely embedded graphs. In Proc. 36th FOCS, pp. 52–61. IEEE Comp. Soc., 1995. [doi:10.1109/SFCS.1995.492462]

[36]   Jon M. Kleinberg and Éva Tardos: Approximations for the disjoint paths problem in high-diameter planar networks. J. Comput. System Sci., 57(1):61–73, 1998. [doi:10.1006/jcss.1998.1579]

[37]   Stavros G. Kolliopoulos and Clifford Stein: Approximating disjoint-path problems using packing integer programs. Math. Programming, 99(1):63–87, 2004. [doi:10.1007/s10107-002-0370-6]

[38]   Mark R. Kramer and Jan van Leeuwen: The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits. Adv. Comput. Res., 2:129–146, 1984.

[39]   Tom Leighton and Satish Rao: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787–832, 1999. [doi:10.1145/331524.331526]

[40]   Richard J. Lipton and Robert Endre Tarjan: A separator theorem for planar graphs. SIAM J. Appl. Math., 36(2):177–189, 1979. [doi:10.1137/0136016]

[41]   James F. Lynch: The equivalence of theorem proving and the interconnection problem. SIGDA Newsl., 5(3):31–36, 1975. [doi:10.1145/1061425.1061430]

[42]   Pasin Manurangsi: Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. In Proc. 49th STOC, pp. 954–961. ACM Press, 2017. [doi:10.1145/3055399.3055412]

[43]   Harald Räcke: Minimizing congestion in general networks. In Proc. 43rd FOCS, pp. 43–52. IEEE Comp. Soc., 2002. [doi:10.1109/SFCS.2002.1181881]

[44]   Prabhakar Raghavan and Clark D. Thompson: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365–374, 1987. [doi:10.1007/BF02579324]

[45]   Prasad Raghavendra and David Steurer: Graph expansion and the unique games conjecture. In Proc. 42nd STOC, pp. 755–764. ACM Press, 2010. [doi:10.1145/1806689.1806792]

[46]   Anup Rao: Parallel repetition in projection games and a concentration bound. SIAM J. Comput., 40(6):1871–1891, 2011. Preliminary version in STOC’08. [doi:10.1137/080734042]

[47]   Satish Rao and Shuheng Zhou: Edge disjoint paths in moderately connected graphs. SIAM J. Comput., 39(5):1856–1887, 2010. [doi:10.1137/080715093]

[48]   Ran Raz: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998. [doi:10.1137/S0097539795280895]

[49]   Neil Robertson and Paul D. Seymour: Outline of a disjoint paths algorithm. In Paths, Flows and VLSI-Layout. Springer, 1990. WorldCat.org.

[50]   Neil Robertson and Paul D. Seymour: Graph minors. XIII. The disjoint paths problem. J. Combin. Theory–B, 63(1):65–110, 1995. [doi:10.1006/jctb.1995.1006]

[51]   Loïc Séguin-Charbonneau and F. Bruce Shepherd: Maximum edge-disjoint paths in planar graphs with congestion 2. Math. Programming, 188:295–317, 2021. Preliminary version in FOCS’11. [doi:10.1007/s10107-020-01513-1]

[52]   Peter Ungar: A theorem on planar graphs. J. London Math. Soc., 26(4):256–262, 1951. [doi:10.1112/jlms/s1-26.4.256]