We give an O(n log log n) time algorithm for computing the minimum cut (or equivalently, the shortest cycle) of a weighted directed planar graph. This improves the previous fastest O(n log3 n) solution. Interestingly, while in undirected planar graphs both min cut and min st-cut have O(n log log n) solutions, in directed planar graphs our result makes min cut faster than min st-cut, which currently requires O(n log n).

We give an $O(n \log^3 n)$ algorithm that, given an $n$-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.

We describe a data structure for submatrix maximum queries in Monge matrices or partial Monge matrices, where a query seeks the maximum element in a contiguous submatrix of the given matrix. The structure, for an n × n Monge matrix, takes O ( n log n ) space and O ( n log n ) preprocessing time, and answers queries in O (log 2 n ) time. For partial Monge matrices, the space grows by α( n ), the preprocessing grows by α( n )log n (α( n ) is the inverse Ackermann function), and the query remains O (log 2 n ). Our design exploits an interpretation of the column maxima in a Monge (partial Monge, respectively) matrix as an upper envelope of pseudo-lines (pseudo-segments, respectively). We give two applications: (1) For a planar set of n points in an axis-parallel rectangle B , we build a data structure, in O ( n α( n )log 4 n ) time and O ( n α( n )log 3 n ) space, that returns, for a query point p , the largest-area empty axis-parallel rectangle contained in B and containing p , in O (log 4 n ) time. This improves substantially the nearly quadratic storage and preprocessing obtained by Augustine et al. [2010]. (2) Given an n -node arbitrarily weighted planar digraph, with possibly negative edge weights, we build, in O ( n log 2 n /log log n ) time, a linear-size data structure that supports edge-weight updates and graph-distance queries between arbitrary pairs of nodes in O ( n 2/3 log 5/3 n ) time per operation. This improves a previous algorithm of Fakcharoenphol and Rao [2006]. Our data structure has already been applied in a recent maximum flow algorithm for planar graphs in Borradaile et al. [2011].

The interval graph for a set of intervals on a line consists of one vertex for each interval and an edge for each intersecting pair of intervals. A probe interval graph is a variant that is motivated by an application to genomics, where the intervals are partitioned into two sets: probes and nonprobes. The graph has an edge between two vertices if they intersect and at least one of them is a probe. We give a linear-time algorithm for determining whether a given graph and partition of vertices into probes and nonprobes is a probe interval graph. If it is, we give a layout of intervals that proves this. We can also determine whether the layout of the intervals is uniquely constrained within the same time bound. As part of the algorithm, we solve the consecutive-ones probe matrix problem in linear time, develop algorithms for operating on PQ trees, and give results that relate PQ trees for different submatrices of a consecutive-ones matrix.

Let $G = (V, E)$ be a planar $n$-vertex digraph. Consider the problem of computing max $st$-flow values in $G$ from a fixed source $s$ to all sinks $t \in V \set minus \{s\}$. We show how to solve this problem in near-linear $O(n \log^3 n)$ time. Previously, nothing better was known than running a single-source single-sink max flow algorithm $n-1$ times, giving a total time bound of $O(n^2 \log n)$ with the algorithm of Borradaile and Klein. An important implication is that all-pairs max $st$-flow values in $G$ can be computed in near-quadratic time. This is close to optimal as the output size is $\Theta(n^2)$. We give a quadratic lower bound on the number of distinct max flow values and an $\Omega(n^3)$ lower bound for the total size of all min cut-sets. This distinguishes the problem from the undirected case where the number of distinct max flow values is $O(n)$. Previous to our result, no algorithm which could solve the all-pairs max flow values problem faster than the time of $\Theta(n^2)$ max-flow computations for every planar digraph was known. This result is accompanied with a data structure that reports min cut-sets. For fixed $s$ and all $t$, after $O(n^{1.5} \log^2 n)$ preprocessing time, it can report the set of arcs $C$ crossing a min $st$-cut in $O(|C|)$ time.

We describe a data structure for submatrix maximum queries in Monge matrices or Monge partial matrices, where a query specifies a contiguous submatrix of the given matrix, and its output is the maximum element of that submatrix. Our data structure for an n × n Monge matrix takes O(n log n) space, O(n log2 n) preprocessing time, and can answer queries in O(log2 n) time. For a Monge partial matrix the space bound and the preprocessing time both grow by the small factor α(n), where α(n) is the inverse Ackermann function. Our design exploits an interpretation of the column maxima in a Monge matrix (resp., Monge partial matrix) as an upper envelope of pseudo-lines (resp., pseudosegments). We give two applications for this data structure: (1) For a set of n points in a rectangle B in the plane, we build a data structure that, given a query point p, returns the largest-area empty axis-parallel rectangle contained in B and containing p, in O(log4 n) time. The preprocessing time is O(nα(n) log4 n), and the space required is O(nα(n) log3 n). This improves substantially a previous data structure of Augustine et al. [arXiv:1004.0558] that requires quadratic space. (2) Given an n-node arbitrarily weighted planar digraph, with possibly negative edge weights, we build, in O(n log2 n/log log n) time, a linear-size data structure that supports edge-weight updates and distance queries between arbitrary pairs of nodes (where the distance is minimum weight of a path in the graph between the pair of nodes), in O(n2/3 log5,3 n) time for each update and query. This improves the O(n4/5 log13/5 n)-time bound of Fakcharoenphol and Rao [JCSS 72, 2006]. Our data structure has already been applied in a recent maximum flow algorithm for planar graphs of Borradaile et al. [FOCS 2011], and we believe it will find additional applications.

We give an O(n log3n) algorithm that, given an n-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes, finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.

Consider the minimum s-t cut problem in an embedded undirected planar graph. Let p be the minimum number of faces that a curve from s to $t$ passes through. If p=1, that is, the vertices s and t are on the boundary of the same face, then the minimum cut can be found in O(n)time. For general planar graphs this cut can be found in O(n log n) time. We unify these results and give an O(n log p) time algorithm. We use cut-cycles to obtain the value of the minimum cut, and study the structure of these cycles to get an efficient algorithm.

We study the min st-cut and max st-flow problems in planar graphs, both in static and in dynamic settings. First, we present an algorithm that given an undirected planar graph and two vertices s and t computes a min st-cut in O(n log log n) time. Second, we show how to achieve the same bound for the problem of computing a max st-flow in an undirected planar graph. These are the first algorithms breaking the O(n log n) barrier for those two problems, which has been standing for more than 25 years. Third, we present a fully dynamic algorithm maintaining the value of the min st-cuts and the max st-flows in an undirected plane graph (i.e., a planar graph with a fixed embedding): our algorithm is able to insert and delete edges and answer queries for min st-cut/max st-flow values between any pair of vertices s and t in O(n(2/3) log(8/3) n) time per operation. This result is based on a new dynamic shortest path algorithm for planar graphs which may be of independent interest. We remark that this is the first known non-trivial dynamic algorithm for min st-cut and max st-flow.