We present a deterministic fully-dynamic data structure for maintaining information about the cut-vertices in a graph; i.e. the vertices whose removal would disconnect the graph. Our data structure supports insertion and deletion of edges, as well as queries to whether a pair of connected vertices are either biconnected, or can be separated by a cutvertex, and in the latter case we support access to separating cutvertices. All update operations are supported in amortized O(log2 n log2 log n) time, and queries take worst-case O(log n log2 log n) time. Note that these time bounds match the current best for deterministic dynamic connectivity up to log log n factors. The previous best algorithm for biconnectivity had an update time of O(logλ n log log n) by Thorup [STOC'00], based on the O(logλ μ n) data structure by Holm, de Lichtenberg, and Thorup [STOC'98]. We obtain our improved running time by a series of reductions from the original problem into well-defined data structure problems. While we do indeed apply the well-known techniques for improving running time of two-edge connectivity [STOC'00, SODA'18], surprisingly, these techniques alone do not lead to an update time of Õ(log³ n), let alone the Õ(log2 n) we give as a final result. Our contributions include a formally defined transient expose operation, which can be thought of as a cheaper read-only expose operation on a top tree. For each vertex in the graph, we maintain a data structure over its neighbors, and in this data structure we apply biasing (twice) to save an Õ(log n) factor (twice, so two Õ(log n) factors). One of these biasing techniques is a new, simple biased disjoint sets data structure, which may be of independent interest. Moreover, in this neighborhood data structure, we facilitate that the vertex can select two VIP neighbors that get special treatment, corresponding to its potentially two neighbors on an exposed path, improving an otherwise log n-time operation down to constant time. It is this combination of VIP neighbors with the transient expose operation that saves an Õ(log n)-factor from another bottleneck. Combining these technical contributions with the well-known techniques for two-edge connectivity [STOC'00, SODA'18], we obtain the desired update times of O(log2 n log2 log n). The near-linear query time follows directly from the usage of transient expose.

We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the maximum out-degree is bounded. On one hand, we show how to orient the edges such that maximum out- degree is proportional to the arboricity α of the graph, in, either, an amortised update time of 𝒪(log2 n log α), or a worst-case update time of 𝒪 (log3 n log α). On the other hand, motivated by applications including dynamic maximal matching, we obtain a different trade-off. Namely, the improved update time of either 𝒪 (log n log α), amortised, or 𝒪(log2 n log α), worst-case, for the problem of maintaining an edge-orientation with at most 𝒪 (α + log n) out-edges per vertex. Finally, all of our algorithms naturally limit the recourse to be polylogarithmic in n and α. Our algorithms adapt to the current arboricity of the graph, and yield improvements over previous work:

Abstract We present a data structure that, given a graph G of n vertices and m edges, and a suitable pair of nested r-divisions of G, preprocesses G in $$O(m+n)$$ O ( m + n ) time and handles any series of edge-deletions in O(m) total time while answering queries to pairwise biconnectivity in worst-case O(1) time. In case the vertices are not biconnected, the data structure can return a cutvertex separating them in worst-case O(1) time. As an immediate consequence, this gives optimal amortized decremental biconnectivity, 2-edge connectivity, and connectivity for large classes of graphs, including planar graphs and other minor free graphs.

We study dynamic planar graphs with $n$ vertices, subject to edge deletion, edge contraction, edge insertion across a face, and the splitting of a vertex in specified corners. We dynamically maintain a combinatorial embedding of such a planar graph, subject to connectivity and $2$-vertex-connectivity (biconnectivity) queries between pairs of vertices. Whenever a query pair is connected and not biconnected, we find the first and last cutvertex separating them. Additionally, we allow local changes to the embedding by flipping the embedding of a subgraph that is connected by at most two vertices to the rest of the graph. We support all queries and updates in deterministic, worst-case, $O(\log^2 n)$ time, using an $O(n)$-sized data structure. Previously, the best bound for fully-dynamic planar biconnectivity (subject to our set of operations) was an amortised $\tilde{O}(\log^3 n)$ for general graphs, and algorithms with worst-case polylogarithmic update times were known only in the partially dynamic (insertion-only or deletion-only) setting.

Many of the classic graph problems cannot be solved in the Massively Parallel Computation setting (MPC) with strongly sublinear space per machine and o(log n) rounds, unless the 1-vs-2 cycles conjecture is false. This is true even on planar graphs. Such problems include, for example, counting connected components, bipartition, minimum spanning tree problem, (approximate) shortest paths, and (approximate) diameter/radius. In this paper, we show a way to get around this limitation. Specifically, we show that if we have a “nice” (for example, straight-line) embedding of the input graph, all the mentioned problems can be solved with O(n2/3+ε) space per machine in O(1) rounds. In conjunction with existing algorithms for computing the Delaunay triangulation, our results imply an MPC algorithm for exact Euclidean minimum spanning thee (EMST) that uses O(n2/3+ε) space per machine and finishes in O(1) rounds. This is the first improvement over a straightforward use of the standard Borävka's algorithm with the Dauleanay triangulation algorithm of Goodrich [SODA 1997] which results in Θ(log n) rounds. This also partially negatively answers a question of Andoni, Nikolov, Onak, and Yaroslavtsev [STOC 2014], asking for lower bounds for exact EMST. We extend our algorithms to work with embeddings consisting of curves that are not “too squiggly” (as formalized by the total absolute curvature). We do this via a new lemma which we believe is of independent interest and could be used to parameterize other geometric problems by the total absolute curvature. We also state several open problems regarding massively parallel computation on planar graphs. * The authors are part of BARC, Basic Algorithms Research Copenhagen, supported by the VILLUM Foundation grant 16582.

A graph has arboricity α if its edges can be partitioned into α forests. The dynamic arboricity decomposition problem is to update a partitioning of the graph’s edges into forests, as a graph undergoes insertions and deletions of edges. We present an algorithm for maintaining partitioning into α+1 forests, provided the arboricity of the dynamic graph never exceeds α. Our algorithm has an update time of Õ(n^{3/4}) when α is at most polylogarithmic in n. Similarly, the dynamic bounded out-orientation problem is to orient the edges of the graph such that the out-degree of each vertex is at all times bounded. For this problem, we give an algorithm that orients the edges such that the out-degree is at all times bounded by α+1, with an update time of Õ(n^{5/7}), when α is at most polylogarithmic in n. Here, the choice of α+1 should be viewed in the light of the well-known lower bound by Brodal and Fagerberg which establishes that, for general graphs, maintaining only α out-edges would require linear update time. However, the lower bound by Brodal and Fagerberg is non-planar. In this paper, we give a lower bound showing that even for planar graphs, linear update time is needed in order to maintain an explicit three-out-orientation. For planar graphs, we show that the dynamic four forest decomposition and four-out-orientations, can be updated in Õ(n^{1/2}) time.

We present a data structure that, given a graph $G$ of $n$ vertices and $m$ edges, and a suitable pair of nested $r$-divisions of $G$, preprocesses $G$ in $O(m+n)$ time and handles any series of edge-deletions in $O(m)$ total time while answering queries to pairwise biconnectivity in worst-case $O(1)$ time. In case the vertices are not biconnected, the data structure can return a cutvertex separating them in worst-case $O(1)$ time. As an immediate consequence, this gives optimal amortized decremental biconnectivity, 2-edge connectivity, and connectivity for large classes of graphs, including planar graphs and other minor free graphs.

We show that every labelled planar graph G can be assigned a canonical embedding φ(G), such that for any planar G’ that differs from G by the insertion or deletion of one edge, the number of local changes to the combinatorial embedding needed to get from φ(G) to φ(G’) is (log n). In contrast, there exist embedded graphs where Ω(n) changes are necessary to accommodate one inserted edge. We provide a matching lower bound of Ω(log n) local changes, and although our upper bound is worst-case, our lower bound hold in the amortized case as well. Our proof is based on BC trees and SPQR trees, and we develop pre-split variants of these for general graphs, based on a novel biased heavy-path decomposition, where the structural changes corresponding to edge insertions and deletions in the underlying graph consist of at most (log n) basic operations of a particularly simple form. As a secondary result, we show how to maintain the pre-split trees under edge insertions in the underlying graph deterministically in worst case (log3 n) time. Using this, we obtain deterministic data structures for incremental planarity testing, incremental planar embedding, and incremental triconnectivity, that each have worst case (log3 n) update and query time, answering an open question by La Poutré and Westbrook from 1998.

Given a dynamic graph subject to insertions and deletions of edges, a natural question is whether the graph presently admits a planar embedding. We give a deterministic fully-dynamic algorithm for general graphs, running in amortized O(log3 n) time per edge insertion or deletion, that maintains a bit indicating whether or not the graph is presently planar. This is an exponential improvement over the previous best algorithm [Eppstein, Galil, Italiano, Spencer, 1996] which spends amortized O(√n) time per update.

Each vertex of an arbitrary simple graph on n vertices chooses k random incident edges. What is the expected number of edges in the original graph that connect different connected components of the sampled subgraph? We prove that the answer is O(n/k), when k ≥ c log n, for some large enough c. We conjecture that the same holds for smaller values of k, possibly for any k ≥ 2. Such a result is best possible for any k ≥ 2. As an application, we use this sampling result to obtain a one-way communication protocol with private randomness for finding a spanning forest of a graph in which each vertex sends only O (√n log n) bits to a referee.

In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one-by-one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes the shortest augmenting path from the newly inserted vertex (denoted the SAP protocol) uses at most amortized O (log 2 n ) replacements per insertion, where n is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for any replacement strategy, almost matching the Ω (log n ) lower bound. The previous best strategy known achieved amortized O (√ n ) replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014]. For the SAP protocol in particular, nothing better than the trivial O ( n ) bound was known except in special cases. Our analysis immediately implies the same upper bound of O (log 2 n ) reassignments for the capacitated assignment problem, where each vertex on the static side of the bipartition is initialized with the capacity to serve a number of vertices. We also analyze the problem of minimizing the maximum server load. We show that if the final graph has maximum server load L , then the SAP protocol makes amortized O (min { L log 2 n , √ n log n }) reassignments. We also show that this is close to tight, because Ω (min { L , √ n }) reassignments can be necessary.

We present a decremental data structure for maintaining the SPQR-tree of a planar graph subject to edge contractions and deletions. The update time, amortized over Omega(n) operations, is O(log^2 n). Via SPQR-trees, we give a decremental data structure for maintaining 3-vertex connectivity in planar graphs. It answers queries in O(1) time and processes edge deletions and contractions in O(log^2 n) amortized time. The previous best supported deletions and insertions in O(sqrt{n}) time.

Given a graph, does there exist an orientation of the edges such that the resulting directed graph is strongly connected? Robbins' theorem [Robbins, Am. Math. Monthly, 1939] asserts that such an orientation exists if and only if the graph is 2-edge connected. A natural extension of this problem is the following: Suppose that the edges of the graph are partitioned into trails. Can the trails be oriented consistently such that the resulting directed graph is strongly connected? We show that 2-edge connectivity is again a sufficient condition and we provide a linear time algorithm for finding such an orientation. The generalised Robbins' theorem [Boesch, Am. Math. Monthly, 1980] for mixed multigraphs asserts that the undirected edges of a mixed multigraph can be oriented to make the resulting directed graph strongly connected exactly when the mixed graph is strongly connected and the underlying graph is bridgeless. We consider the natural extension where the undirected edges of a mixed multigraph are partitioned into trails. It turns out that in this case the condition of the generalised Robbin's Theorem is not sufficient. However, we show that as long as each cut either contains at least 2 undirected edges or directed edges in both directions, there exists an orientation of the trails such that the resulting directed graph is strongly connected. Moreover, if the condition is satisfied, we may start by orienting an arbitrary trail in an arbitrary direction. Using this result one obtains a very simple polynomial time algorithm for finding a strong trail orientation if it exists, both in the undirected and the mixed setting.

In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes the shortest augmenting path from the newly inserted vertex (denoted the SAP protocol) uses at most amortized replacements per insertion, where n is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for any replacement strategy, almost matching the Ω(log n) lower bound. The previous best strategy known achieved amortized replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014]. For the SAP protocol in particular, nothing better than then trivial bound was known except in special cases. Our analysis immediately implies the same upper bound of reassignments for the capacitated assignment problem, where each vertex on the static side of the bipartition is initialized with the capacity to serve a number of vertices. We also analyze the problem of minimizing the maximum server load. We show that if the final graph has maximum server load L, then the SAP protocol makes amortized reassignments. We also show that this is close to tight because reassignments can be necessary.

We present a deterministic fully-dynamic data structure for maintaining information about the bridges in a graph. We support updates in Õ((log n)2) amortized time, and can find a bridge in the component of any given vertex, or a bridge separating any two given vertices, in

We answer the following question dating back to J.E. Littlewood (1885-1977): Can two lions catch a man in a bounded area with rectifiable lakes? The lions and the man are all assumed to be points moving with at most unit speed. That the lakes are rectifiable means that their boundaries are finitely long. This requirement is to avoid pathological examples where the man survives forever because any path to the lions is infinitely long. We show that the answer to the question is not always "yes", by giving an example of a region R in the plane where the man has a strategy to survive forever. R is a polygonal region with holes and the exterior and interior boundaries are pairwise disjoint, simple polygons. Our construction is the first truly two-dimensional example where the man can survive. Next, we consider the following game played on the entire plane instead of a bounded area: There is any finite number of unit speed lions and one fast man who can run with speed 1+epsilon for some value epsilon>0. Can the man always survive? We answer the question in the affirmative for any constant epsilon>0.

We present a data structure that can maintain a simple planar graph under edge contractions in linear total time. The data structure supports adjacency queries and provides access to neighbor lists in $O(1)$ time. Moreover, it can report all the arising self-loops and parallel edges. By applying the data structure, we can achieve optimal running times for decremental bridge detection, 2-edge connectivity, maximal 3-edge connected components, and the problem of finding a unique perfect matching for a static planar graph. Furthermore, we improve the running times of algorithms for several planar graph problems, including decremental 2-vertex and 3-edge connectivity, and we show that using our data structure in a black-box manner, one obtains conceptually simple optimal algorithms for computing MST and 5-coloring in planar graphs.

A graph U is an induced universal graph for a family F of graphs if every graph in F is a vertex-induced subgraph of U. We give upper and lower bounds for the size of induced universal graphs for the family of graphs with n vertices of maximum degree D. Our new bounds improve several previous results except for the special cases where D is either near-constant or almost n/2. For constant even D Butler [Graphs and Combinatorics 2009] has shown O(n^(D/2)) and recently Alon and Nenadov [SODA 2017] showed the same bound for constant odd D. For constant D Butler also gave a matching lower bound. For generals graphs, which corresponds to D = n, Alon [Geometric and Functional Analysis, to appear] proved the existence of an induced universal graph with (1+o(1)) \cdot 2^((n-1)/2) vertices, leading to a smaller constant than in the previously best known bound of 16 * 2^(n/2) by Alstrup, Kaplan, Thorup, and Zwick [STOC 2015]. In this paper we give the following lower and upper bound of binom(floor(n/2))(floor(D/2)) * n^(-O(1)) and binom(floor(n/2))(floor(D/2)) * 2^(O(sqrt(D log D) * log(n/D))), respectively, where the upper bound is the main contribution. The proof that it is an induced universal graph relies on a randomized argument. We also give a deterministic upper bound of O(n^k / (k-1)!). These upper bounds are the best known when D <= n/2 - tilde-Omega(n^(3/4)) and either D is even and D = omega(1) or D is odd and D = omega(log n/log log n). In this range we improve asymptotically on the previous best known results by Butler [Graphs and Combinatorics 2009], Esperet, Arnaud and Ochem [IPL 2008], Adjiashvili and Rotbart [ICALP 2014], Alon and Nenadov [SODA 2017], and Alon [Geometric and Functional Analysis, to appear].

We show how to represent a planar digraph in linear space so that reach ability queries can be answered in constant time. The data structure can be constructed in linear time. This representation of reach ability is thus optimal in both time and space, and has optimal construction time. The previous best solution used O(n log n) space for constant query time [Thorup FOCS'01].

We present an algorithm to support the dynamic embedding in the plane of a dynamic graph. An edge can be inserted across a face between two vertices on the boundary (we call such a vertex pair linkable), and edges can be deleted. The planar embedding can also be changed locally by flipping components that are connected to the rest of the graph by at most two vertices. Given vertices u,v, linkable(u,v) decides whether u and v are linkable, and if so, returns a list of suggestions for the placement of (u,v) in the embedding. For non-linkable vertices u,v, we define a new query, one-flip-linkable(u,v) providing a suggestion for a flip that will make them linkable if one exists. We will support all updates and queries in O(log^2 n) time. Our time bounds match those of Italiano et al. for a static (flipless) embedding of a dynamic graph. Our new algorithm is simpler, exploiting that the complement of a spanning tree of a connected plane graph is a spanning tree of the dual graph. The primal and dual trees are interpreted as having the same Euler tour, and a main idea of the new algorithm is an elegant interaction between top trees over the two trees via their common Euler tour.

We design top trees as a new simpler interface for data structures maintaining information in a fully dynamic forest. We demonstrate how easy and versatile they are to use on a host of different applications. For example, we show how to maintain the diameter, center, and median of each tree in the forest. The forest can be updated by insertion and deletion of edges and by changes to vertex and edge weights. Each update is supported in O (log n ) time, where n is the size of the tree(s) involved in the update. Also, we show how to support nearest common ancestor queries and level ancestor queries with respect to arbitrary roots in O (log n ) time. Finally, with marked and unmarked vertices, we show how to compute distances to a nearest marked vertex. The latter has applications to approximate nearest marked vertex in general graphs, and thereby to static optimization problems over shortest path metrics.Technically speaking, top trees are easily implemented either with Frederickson's [1997a] topology trees or with Sleator and Tarjan's [1983] dynamic trees. However, we claim that the interface is simpler for many applications, and indeed our new bounds are quadratic improvements over previous bounds where they exist.

Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a graph with n vertices, the amortized operation costs are O (log 2 n ) for connectivity, O (log 4 n ) for minimum spanning forest, 2-edge connectivity, and O (log 5 n ) biconnectivity.

Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning forest, a-edge connectivity, and biconnectivity.Assuming that we start with no edges in a graph with n vertices, the amortized operation cost0 arc O(log2 n) for connectivity and O(log4 n) for minimum spanning forest, 2+dgeconnectivity, and biconnectity.