English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Voronoi diagrams technique was introduced by Cabello to compute thediameter of planar graphs in subquadratic time. We present novel applicationsof this technique in static, fault-tolerant, and partially-dynamic undirectedunweighted 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$D<n^{1/3}$ or $D>n^{2/3}$.  2. In the fault-tolerant setting, we give an $n^{7/3+o(1)}$ time algorithmfor computing the diameter of $G\setminus \{e\}$ for every edge $e$ in $G$ thereplacement diameter problem. Compared to the naive $\tilde{O}(n^{8/3})$ timealgorithm that runs the static algorithm for every edge.  3. In the incremental setting, where we wish to maintain the diameter whilewhile 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 thatruns 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 decrementalupdates.  Our upper bounds are obtained by novel uses and manipulations of Voronoidiagrams. These include maintaining the Voronoi diagram when edges of the graphare deleted, allowing the sites of the Voronoi diagram to lie on a BFS treelevel (rather than on boundaries of $r$-division), and a new reduction fromincremental diameter to incremental distance oracles that could be of interestbeyond planar graphs. Our lower bound is the first lower bound for a dynamicplanar graph problem that is conditioned on the SETH.

What Else Can Voronoi Diagrams Do For Diameter In Planar Graphs?