Dynamic Time Warping (DTW) distance is the optimal cost of matching two strings when extending runs of letters is for free. Therefore, it is natural to measure the time complexity of DTW in terms of the number of runs n (rather than the string lengths N). In this paper, we give an Õ(n²) time algorithm for computing the DTW distance. This matches (up to log factors) the known (conditional) lower bound, and should be compared with the previous fastest O(n³) time exact algorithm and the Õ(n²) time approximation algorithm. Our method also immediately implies an Õ(nk) time algorithm when the distance is bounded by k. This should be compared with the previous fastest O(n²k) and O(Nk) time exact algorithms and the Õ(nk) time approximation algorithm.

Abstract We give a randomized algorithm that finds a minimum cut in an undirected weighted m-edge n-vertex graph G with high probability in $$O(m \log ^2 n)$$ O ( m log 2 n ) time. This is the first improvement to Karger’s celebrated $$O(m \log ^3 n)$$ O ( m log 3 n ) time algorithm from 1996. Our main technical contribution is a deterministic $$O(m \log n)$$ O ( m log n ) time algorithm that, given a spanning tree T of G, finds a minimum cut of G that 2-respects (cuts two edges of) T.

The Voronoi diagrams technique was introduced by Cabello to compute the diameter of planar graphs in subquadratic time. We present novel applications of this technique in static, fault-tolerant, and partially-dynamic undirected unweighted planar graphs, as well as some new limitations. 1. In the static case, we give $n^{3+o(1)}/D^2$ and $\tilde{O}(n\cdot D^2)$ time algorithms for computing the diameter of a planar graph $G$ with diameter $D$. These are faster than the state of the art $\tilde{O}(n^{5/3})$ when $Dn^{2/3}$. 2. In the fault-tolerant setting, we give an $n^{7/3+o(1)}$ time algorithm for computing the diameter of $G\setminus \{e\}$ for every edge $e$ in $G$ the replacement diameter problem. Compared to the naive $\tilde{O}(n^{8/3})$ time algorithm that runs the static algorithm for every edge. 3. In the incremental setting, where we wish to maintain the diameter while while adding edges, we present an algorithm with total running time $n^{7/3+o(1)}$. Compared to the naive $\tilde{O}(n^{8/3})$ time algorithm that runs the static algorithm after every update. 4. We give a lower bound (conditioned on the SETH) ruling out an amortized $O(n^{1-\varepsilon})$ update time for maintaining the diameter in *weighted* planar graph. The lower bound holds even for incremental or decremental updates. Our upper bounds are obtained by novel uses and manipulations of Voronoi diagrams. These include maintaining the Voronoi diagram when edges of the graph are deleted, allowing the sites of the Voronoi diagram to lie on a BFS tree level (rather than on boundaries of $r$-division), and a new reduction from incremental diameter to incremental distance oracles that could be of interest beyond planar graphs. Our lower bound is the first lower bound for a dynamic planar graph problem that is conditioned on the SETH.

We consider the problem of preprocessing a weighted directed planar graph in order to quickly answer exact distance queries. The main tension in this problem is between space S and query time Q , and since the mid-1990s all results had polynomial time-space tradeoffs, e.g., Q = ~ Θ( n/√ S ) or Q = ~Θ( n 5/2 /S 3/2 ). In this article we show that there is no polynomial tradeoff between time and space and that it is possible to simultaneously achieve almost optimal space n 1+ o (1) and almost optimal query time n o (1) . More precisely, we achieve the following space-time tradeoffs: n 1+ o (1) space and log 2+ o (1) n query time, n log 2+ o (1) n space and n o (1) query time, n 4/3+ o (1) space and log 1+ o (1) n query time. We reduce a distance query to a variety of point location problems in additively weighted Voronoi diagrams and develop new algorithms for the point location problem itself using several partially persistent dynamic tree data structures.

Given two strings S and P, the Episode Matching problem is to find the shortest substring of S that contains P as a subsequence. The best known upper bound for this problem is Õ(nm) by Das et al. (1997), where n,m are the lengths of S and P, respectively. Although the problem is well studied and has many applications in data mining, this bound has never been improved. In this paper we show why this is the case by proving that no O((nm)^{1-ε}) algorithm (even for binary strings) exists, unless the Strong Exponential Time Hypothesis (SETH) is false. We then consider the indexing version of the problem, where S is preprocessed into a data structure for answering episode matching queries P. We show that for any τ, there is a data structure using O(n+(n/(τ)) ^k) space that answers episode matching queries for any P of length k in O(k⋅ τ ⋅ log log n) time. We complement this upper bound with an almost matching lower bound, showing that any data structure that answers episode matching queries for patterns of length k in time O(n^δ), must use Ω(n^{k-kδ-o(1)}) space, unless the Strong k-Set Disjointness Conjecture is false. Finally, for the special case of k = 2, we present a faster construction of the data structure using fast min-plus multiplication of bounded integer matrices.

We consider exact distance oracles for directed weighted planar graphs in the presence of failing vertices. Given a source vertex u , a target vertex v and a set X of k failed vertices, such an oracle returns the length of a shortest u -to- v path that avoids all vertices in X . We propose oracles that can handle any number k of failures. We show several tradeoffs between space, query time, and preprocessing time. In particular, for a directed weighted planar graph with n vertices and any constant k , we show an Õ( n )-size, Õ(√ n )-query-time oracle. 1 We then present a space vs. query time tradeoff: for any q ε [ 1,√ n ], we propose an oracle of size n k+1+o(1) / q 2k that answers queries in Õ( q ) time. For single vertex failures ( k = 1), our n 2+o(1) / q 2 -size, Õ( q )-query-time oracle improves over the previously best known tradeoff of Baswana et al. SODA 2012 by polynomial factors for q ≥ n t , for any t ∈ (0,1/2]. For multiple failures, no planarity exploiting results were previously known.

We consider the problem of preprocessing two strings S and T, of lengths m and n, respectively, in order to be able to efficiently answer the following queries: Given positions i,j in S and positions a,b in T, return the optimal alignment score of S[i..j] and T[a..b]. Let N = mn. We present an oracle with preprocessing time N^{1+o(1)} and space N^{1+o(1)} that answers queries in log^{2+o(1)}N time. In other words, we show that we can efficiently query for the alignment score of every pair of substrings after preprocessing the input for almost the same time it takes to compute just the alignment of S and T. Our oracle uses ideas from our distance oracle for planar graphs [STOC 2019] and exploits the special structure of the alignment graph. Conditioned on popular hardness conjectures, this result is optimal up to subpolynomial factors. Our results apply to both edit distance and longest common subsequence (LCS). The best previously known oracle with construction time and size 𝒪(N) has slow Ω(√N) query time [Sakai, TCS 2019], and the one with size N^{1+o(1)} and query time log^{2+o(1)}N (using a planar graph distance oracle) has slow Ω(N^{3/2}) construction time [Long & Pettie, SODA 2021]. We improve both approaches by roughly a √ N factor.

We give an $O(k^3 n \log n \min(k,\log^2 n) \log^2(nC))$-time algorithm for computing maximum integer flows in planar graphs with integer arc {\em and vertex} capacities bounded by $C$, and $k$ sources and sinks. This improves by a factor of $\max(k^2,k\log^2 n)$ over the fastest algorithm previously known for this problem [Wang, SODA 2019]. The speedup is obtained by two independent ideas. First we replace an iterative procedure of Wang that uses $O(k)$ invocations of an $O(k^3 n \log^3 n)$-time algorithm for maximum flow algorithm in a planar graph with $k$ apices [Borradaile et al., FOCS 2012, SICOMP 2017], by an alternative procedure that only makes one invocation of the algorithm of Borradaile et al. Second, we show two alternatives for computing flows in the $k$-apex graphs that arise in our modification of Wang's procedure faster than the algorithm of Borradaile et al. In doing so, we introduce and analyze a sequential implementation of the parallel highest-distance push-relabel algorithm of Goldberg and Tarjan~[JACM 1988].

Given an undirected, unweighted planar graph $G$ with $n$ vertices, we present a truly subquadratic size distance oracle for reporting exact shortest-path distances between any pair of vertices of $G$ in constant time. For any $\varepsilon > 0$, our distance oracle takes up $O(n^{5/3+\varepsilon})$ space and is capable of answering shortest-path distance queries exactly for any pair of vertices of $G$ in worst-case time $O(\log (1/\varepsilon))$. Previously no truly sub-quadratic size distance oracles with constant query time for answering exact all-pairs shortest paths distance queries existed.

Given an edge-weighted directed graph G, the Negative-k-Cycle problem asks whether G contains a negative-weight cycle with at most k edges. For k = 3 the problem is known as the NegativeTriangle problem and is equivalent to all-pairs shortest paths (and to min-plus matrix multiplication) and solvable in O(n3) time. In this paper, we consider the case of directed planar graphs. We show that the Negative-k-Cycle problem can be solved in min{O(nk2 log n), O(n2)} time. Assuming the min-plus convolution conjecture, we then show, for k > n1/3 that there is no algorithm polynomially faster than , and for k ≤ n1/3 that our O(nk2 log n) upper bound is essentially tight. The latter gives the first non-trivial tight bounds for a planar graph problem in P. Our lower bounds are obtained by introducing a natural problem on matrices that generalizes both min-plus matrix multiplication and min-plus convolution, and whose complexity lies between the complexities of these two problems.

We present an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs. Let $G$ be a planar graph with $n$ vertices and $b$ sites that lie on a constant number of faces. We show how to preprocess $G$ in $\tilde O(nb^2)$ time so that one can compute any additively weighted Voronoi diagram for these sites in $\tilde O(b)$ time. We use this construction to compute the diameter of a directed planar graph with real arc lengths in $\tilde{O}(n^{5/3})$ time. This improves the recent breakthrough result of Cabello [ SODA 2017, SIAM, Philadelphia, 2017, pp. 2143--2152], both by improving the running time (from $\tilde{O}(n^{11/6})$), and by providing a deterministic algorithm. It is in fact the first truly subquadratic deterministic algorithm for this problem. Our use of Voronoi diagrams to compute the diameter follows that of Cabello, but he used abstract Voronoi diagrams, which makes his diameter algorithm more involved, more expensive, and randomized. As in Cabello's work, our algorithm can compute, for every vertex $v$, both the farthest vertex from $v$ (i.e., the eccentricity of $v$), and the sum of distances from $v$ to all other vertices. Hence, our algorithm can also compute the radius, median, and Wiener index (sum of all pairwise distances) of a planar graph within the same time bounds. Our construction of Voronoi diagrams for planar graphs is of independent interest.

We consider the problem of dynamically maintaining an optimal alignment of two strings, each of length at most n, as they undergo insertions, deletions, and substitutions of letters. The string alignment problem generalizes the longest common subsequence (LCS) problem and the edit distance problem (also with non-unit costs, as long as insertions and deletions cost the same). The conditional lower bound of Backurs and Indyk [J. Comput. 2018] for computing the LCS in the static case implies that strongly sublinear update time for the dynamic string alignment problem would refute the Strong Exponential Time Hypothesis. We essentially match this lower bound when the alignment weights are constants, by showing how to process each update in 𝒪̃(n) time. When the weights are integers bounded in absolute value by some w=n^{𝒪(1)}, we can maintain the alignment in 𝒪̃(n ⋅ min {√ n,w}) time per update. For the 𝒪̃(nw)-time algorithm, we heavily rely on Tiskin’s work on semi-local LCS, and in particular, in an implicit way, on his algorithm for computing the (min,+)-product of two simple unit-Monge matrices [Algorithmica 2015]. As for the 𝒪̃(n√n)-time algorithm, we employ efficient data structures for computing distances in planar graphs.

We give a randomized algorithm that finds a minimum cut in an undirected weighted $m$-edge $n$-vertex graph $G$ with high probability in $O(m \log^2 n)$ time. This is the first improvement to Karger's celebrated $O(m \log^3 n)$ time algorithm from 1996. Our main technical contribution is a deterministic $O(m \log n)$ time algorithm that, given a spanning tree $T$ of $G$, finds a minimum cut of $G$ that 2-respects (cuts two edges of) $T$.

The edit distance between two rooted ordered trees with n nodes labeled from an alphabet Ʃ is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. Tree edit distance is a well-known generalization of string edit distance. The fastest known algorithm for tree edit distance runs in cubic O ( n 3 ) time and is based on a similar dynamic programming solution as string edit distance. In this article, we show that a truly subcubic O ( n 3-ε ) time algorithm for tree edit distance is unlikely: For |Ʃ| = Ω ( n ), a truly subcubic algorithm for tree edit distance implies a truly subcubic algorithm for the all pairs shortest paths problem. For |Ʃ| = O (1), a truly subcubic algorithm for tree edit distance implies an O ( n k-ε ) algorithm for finding a maximum weight k -clique. Thus, while in terms of upper bounds string edit distance and tree edit distance are highly related, in terms of lower bounds string edit distance exhibits the hardness of the strong exponential time hypothesis (Backurs, Indyk STOC’15) whereas tree edit distance exhibits the hardness of all pairs shortest paths. Our result provides a matching conditional lower bound for one of the last remaining classic dynamic programming problems.

We present an optimal data structure for submatrix maximum queries in n × n Monge matrices. Our result is a two-way reduction showing that the problem is equivalent to the classical predecessor problem in a universe of polynomial size. This gives a data structure of O ( n ) space that answers submatrix maximum queries in O (log log n ) time, as well as a matching lower bound, showing that O (log log n ) query-time is optimal for any data structure of size O ( n polylog( n )). Our result settles the problem, improving on the O (log 2 n ) query time in SODA’12, and on the O (log n ) query-time in ICALP’14. In addition, we show that partial Monge matrices can be handled in the same bounds as full Monge matrices. In both previous results, partial Monge matrices incurred additional inverse-Ackermann factors.

We consider exact distance oracles for directed weighted planar graphs in the presence of failing vertices. Given a source vertex u, a target vertex v and a set X of k failed vertices, such an oracle returns the length of a shortest u-to-v path that avoids all vertices in X. We propose oracles that can handle any number k of failures. More specifically, for a directed weighted planar graph with n vertices, any constant k, and for any q ∊ [1, ], we propose an oracle of size that answers queries in Õ(q) time.1 In particular, we show an Õ(n)-size, -query-time oracle for any constant k. This matches, up to polylogarithmic factors, the fastest failure-free distance oracles with nearly linear space. For single vertex failures (k = 1), our -size, Õ(q)-query-time oracle improves over the previously best known tradeoff of Baswana et al. [SODA 2012] by polynomial factors for q = Ω(nt), t ∊ (1/4, 1/2]. For multiple failures, no planarity exploiting results were previously known.

We present new tradeoffs between space and query-time for exact distance oracles in directed weighted planar graphs. These tradeoffs are almost optimal in the sense that they are within polylogarithmic, subpolynomial or arbitrarily small polynomial factors from the naïve linear space, constant query-time lower bound. These tradeoffs include: (i) an oracle with space O(n1+є) and query-time Õ(1) for any constant є>0, (ii) an oracle with space Õ(n) and query-time O(nє) for any constant є>0, and (iii) an oracle with space n1+o(1) and query-time no(1).

Given a graph G and a set of terminals T, a distance emulator of G is another graph H (not necessarily a subgraph of G) containing T, such that all the pairwise distances in G between vertices of T are preserved in H. An important open question is to find the smallest possible distance emulator. We prove that, given any subset of k terminals in an n-vertex undirected unweighted planar graph, we can construct in O~(n) time a distance emulator of size O~(min(k^2,sqrt{k * n})). This is optimal up to logarithmic factors. The existence of such distance emulator provides a straightforward framework to solve distance-related problems on planar graphs: Replace the input graph with the distance emulator, and apply whatever algorithm available to the resulting emulator. In particular, our result implies that, on any unweighted undirected planar graph, one can compute all-pairs shortest path distances among k terminals in O~(n) time when k=O(n^{1/3}).

The Planar Graph Metric Compression Problem is to compactly encode the distances among k nodes in a planar graph of size n. Two naïve solutions are to store the graph using O(n) bits, or to explicitly store the distance matrix with O(k2 log n) bits. The only lower bounds are from the seminal work of Gavoille, Peleg, Prennes, and Raz [SODA’01], who rule out compressions into a polynomially smaller number of bits, for weighted planar graphs, but leave a large gap for unweighted planar graphs. For example, when , the upper bound is O(n) and their constructions imply an Ω(n3/4) lower bound. This gap is directly related to other major open questions in labeling schemes, dynamic algorithms, and compact routing. Our main result is a new compression of the planar graph metric into bits, which is optimal up to log factors. Our data structure circumvents an Õ(k2) lower bound of Krauthgamer, Nguyen, and Zondiner [SIDMA’14] for compression using minors, and the lower bound of Gavoille et al. for compression of weighted planar graphs. This is an unexpected and decisive proof that weights can make planar graphs inherently more complex. Moreover, we design a new Subset Distance Oracle for planar graphs with space, and Õ(n3/4) query time. Our work carries strong messages to related fields. In particular, the famous O(n1/2) vs. Ω(n1/3) gap for distance labeling schemes in planar graphs cannot be resolved with the current lower bound techniques. On the positive side, we introduce the powerful tool of unit-monge to planar graph algorithms.

The edit distance between two rooted ordered trees with n nodes labeled from an alphabet Σ is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. Tree edit distance is a well known generalization of string edit distance. The fastest known algorithm for tree edit distance runs in cubic O(n3) time and is based on a similar dynamic programming solution as string edit distance. In this paper we show that a truly subcubic O(n3–ε) time algorithm for tree edit distance is unlikely: For |Σ| = Ω(n), a truly subcubic algorithm for tree edit distance implies a truly subcubic algorithm for the all pairs shortest paths problem. For |Σ| = O(1), a truly subcubic algorithm for tree edit distance implies an O(nk–ε) algorithm for finding a maximum weight k-clique. Thus, while in terms of upper bounds string edit distance and tree edit distance are highly related, in terms of lower bounds string edit distance exhibits the hardness of the strong exponential time hypothesis [Backurs, Indyk STOC’15] whereas tree edit distance exhibits the hardness of all pairs shortest paths. Our result provides a matching conditional lower bound for one of the last remaining classic dynamic programming problems.

We present an efficient construction of additively weighted Voronoi diagrams on planar graphs. Let G be a planar graph with n vertices and b sites that lie on a constant number of faces. We show how to preprocess G in Õ(nb2) time1 so that one can compute any additively weighted Voronoi diagram for these sites in Õ(b) time. We use this construction to compute the diameter of a directed planar graph with real arc lengths in Õ(n5/3) time. This improves the recent breakthrough result of Cabello (SODA’17), both by improving the running time (from Õ(n11/6)), and by providing a deterministic algorithm. It is in fact the first truly subquadratic deterministic algorithm for this problem. Our use of Voronoi diagrams to compute the diameter follows that of Cabello, but he used abstract Voronoi diagrams, which makes his diameter algorithm more involved, more expensive, and randomized. As in Cabello's work, our algorithm can also compute the Wiener index of a planar graph (i.e., the sum of all pairwise distances) within the same bound. Our construction of Voronoi diagrams for planar graphs is of independent interest. It has already been used to obtain fast exact distance oracles for planar graphs [Cohen-Addad et al., FOCS’17].

We present an O(n1.5)-space distance oracle for directed planar graphs that answers distance queries in O(log n) time. Our oracle both significantly simplifies and significantly improves the recent oracle of Cohen-Addad, Dahlgaard and Wulff-Nilsen [FOCS 2017], which uses O(n5/3)-space and answers queries in O(log n) time. We achieve this by designing an elegant and efficient point location data structure for Voronoi diagrams on planar graphs. We further show a smooth tradeoff between space and query-time. For any S ∊ [n, n2], we show an oracle of size S that answers queries in Õ(max{1, n1.5/S}) time. This new tradeoff is currently the best (up to polylogarithmic factors) for the entire range of S and improves by polynomial factors over all previously known tradeoffs for the range S ∊ [n, n5/3].

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).

In the $k$-dispersion problem, we need to select $k$ nodes of a given graph so as to maximize the minimum distance between any two chosen nodes. This can be seen as a generalization of the independent set problem, where the goal is to select nodes so that the minimum distance is larger than 1. We design an optimal $O(n)$ time algorithm for the dispersion problem on trees consisting of $n$ nodes, thus improving the previous $O(n\log n)$ time solution from 1997. We also consider the weighted case, where the goal is to choose a set of nodes of total weight at least $W$. We present an $O(n\log^2n)$ algorithm improving the previous $O(n\log^4 n)$ solution. Our solution builds on the search version (where we know the minimum distance $λ$ between the chosen nodes) for which we present tight $Θ(n\log n)$ upper and lower bounds.

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].

We start a systematic study of data structures for the nearest colored node problem on trees. Given a tree with colored nodes and weighted edges, we want to answer queries (v,c) asking for the nearest node to node v that has color c. This is a natural generalization of the well-known nearest marked ancestor problem. We give an O(n)-space O(log log n)-query solution and show that this is optimal. We also consider the dynamic case where updates can change a node's color and show that in O(n) space we can support both updates and queries in O(log n) time. We complement this by showing that O(polylog n) update time implies Omega(log n \ log log n) query time. Finally, we consider the case where updates can change the edges of the tree (link-cut operations). There is a known (top-tree based) solution that requires update time that is roughly linear in the number of colors. We show that this solution is probably optimal by showing that a strictly sublinear update time implies a strictly subcubic time algorithm for the classical all pairs shortest paths problem on a general graph. We also consider versions where the tree is rooted, and the query asks for the nearest ancestor/descendant of node v that has color c, and present efficient data structures for both variants in the static and the dynamic setting.

Given an undirected graph with edge costs and node weights, the minimum bisection problem asks for a partition of the nodes into two parts of equal weight such that the sum of edge costs between the parts is minimized. We give a polynomial time bicriteria approximation scheme for bisection on planar graphs. Specifically, let W be the total weight of all nodes in a planar graph G. For any constant ε > 0, our algorithm outputs a bipartition of the nodes such that each part weighs at most W/2 + ε and the total cost of edges crossing the partition is at most (1+ε) times the total cost of the optimal bisection. The previously best known approximation for planar minimum bisection, even with unit node weights, was ~O(log n). Our algorithm actually solves a more general problem where the input may include a target weight for the smaller side of the bipartition.

We provide an implementation of an algorithm that, given a triangulated planar graph with m edges, returns a simple cycle that is a 2/3-balanced separator consisting of at most edges. An efficient construction of a short and balanced separator that forms a simple cycle is essential in numerous planar graph algorithms, e.g., for computing shortest paths, minimum cuts, or maximum flows. To the best of our knowledge, this is the first implementation of such a cycle separator algorithm with a worst-case guarantee on the cycle length. We evaluate the performance of our algorithm and compare it to the planar separator algorithms recently studied by Holzer et al. [ESA 2005, ACM Journal of Experimental Algorithms 2009]. Out of these algorithms, only the Fundamental Cycle Separator (FCS) produces a simple cycle separator. However, FCS does not provide a worst-case size guarantee. We demonstrate that (i) our algorithm is competitive across all test cases in terms of running time, balance and cycle length, (ii) it provides worst-case guarantees on the cycle length, significantly outperforming FCS on some instances, and (iii) it scales to large graphs.

Given a triangulated planar graph G on n vertices and an integer r

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 present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the following:1 Given a desired space allocation S ∊ [n lg lg n, n2], we show how to construct in Õ(S) time a data structure of size O(S) that answers distance queries in Õ(n/ √S) time per query. The best distance oracles for planar graphs until the current work are due to Cabello (SODA 2006), Chen and Xu (STOC 2000), Djidjev (WG 1996), and Fakcharoenphol and Rao (FOCS 2001). For σ ∊ (1, 4/3) and space S = nσ, we essentially improve the query time from n2/S to . As a consequence, we obtain an improvement over the fastest algorithm for k–many distances in planar graphs whenever k ∊ [√n, n). We provide a linear-space exact distance oracle for planar graphs with query time O(n1/2 + ε) for any constant ε > 0. This is the first such data structure with provable sublinear query time. For edge lengths ≥ 1, we provide an exact distance oracle of space Õ(n) such that for any pair of nodes at distance ℓ the query time is Õ(min{ℓ, √n}). Comparable query performance had been observed experimentally but could not be explained theoretically. Our data structures with superlinear space are based on the following new tool: given a non-self-crossing cycle C with c = O(√n) nodes, we can preprocess G in Õ(n) time to produce a data structure of size O(n lg lg c) that can answer the following queries in Õ(c) time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and provides an alternative for a related data structure of Klein (SODA 2005), which reports distances to the boundary of a face, rather than a cycle.

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.

We give an O ( n log 2 n )-time, linear-space algorithm that, given a directed planar graph with positive and negative arc-lengths, and given a node s , finds the distances from s to all nodes.

We give an O(n log2 n)-time, linear-space algorithm that, given a directed planar graph with positive and negative arc-lengths, and given a node s, finds the distances from s to all nodes. The best previously known algorithm requires O(nlog3 n) time and O(n log n) space.

The edit distance between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. In this article, we present a worst-case O ( n 3 )-time algorithm for the problem when the two trees have size n , improving the previous best O ( n 3 log n )-time algorithm. Our result requires a novel adaptive strategy for deciding how a dynamic program divides into subproblems, together with a deeper understanding of the previous algorithms for the problem. We prove the optimality of our algorithm among the family of decomposition strategy algorithms—which also includes the previous fastest algorithms—by tightening the known lower bound of Ω( n 2 log 2 n ) to Ω( n 3 ), matching our algorithm's running time. Furthermore, we obtain matching upper and lower bounds for decomposition strategy algorithms of Θ( nm 2 (1 + log n / m )) when the two trees have sizes m and n and m < n .