Uncrossed Multiflows and Applications to Disjoint Paths

A multiflow in a planar graph is uncrossed if its support paths do not cross. Recently such flows played a role in approximation algorithms for maximum disjoint paths in "fully-planar" instances, where the combined supply-demand graph is planar, as well as low-congestion unsplittable flows for fully-planar and single-source instances. We expand on the theory of uncrossed flows to investigate their utility more generally. We ask three key questions. First, are there other interesting planar multiflow instances that admit uncrossed flows? We answer affirmatively, demonstrating a new family of "pairwise-planar" instances whose flows can be uncrossed. This family subsumes fully-planar but includes substantially more, such as fully-compliant series-parallel instances, and has instances with clique demand graphs. Second, given a fractional uncrossed flow, can we always round it to a "good" integral flow? We again answer positively. For maximization problems (where we maximize the total amount of flow), we obtain integral flows with a constant fraction of the original value. For congestion problems (where we fully route specific given demands), we obtain integral flows with edge congestion 2, or unsplittable flows with an additional additive error. As a consequence we obtain approximation algorithms for maximum disjoint paths and minimum congestion integer multiflow for pairwise-planar instances. Finally, given a planar multiflow instance, can we determine if there exists a congestion 1 uncrossed fractional flow (congestion) or find the highest value uncrossed fractional flow (maximization)? For the congestion model, we show this is NP-hard, but finding uncrossed edge-disjoint paths is polytime solvable if the demands span a bounded number of faces. For the maximization model, we present a strong inapproximability result.