Voronoi diagrams on planar graphs, and computing the diameter in deterministic O(n^5/3) time

MaRDI QIDQ4607914zbMATH OpenFDO

Authors Paweł Gawrychowski, Haim Kaplan, Shay Mozes, Oren Weimann, Micha Sharir

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1704.02793, http://dl.acm.org/citation.cfm?id=3175303

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• Faster Approximate Diameter and Distance Oracles in Planar Graphs
• Faster approximate diameter and distance oracles in planar graphs
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs

Cited in

(16)

• Faster approximate diameter and distance oracles in planar graphs
• The inverse Voronoi problem in graphs. I: Hardness
• Eccentricity queries and beyond using hub labels
• Beyond Helly graphs: the diameter problem on absolute retracts
• Distance problems within Helly graphs and \(k\)-Helly graphs
• Improved bounds for shortest paths in dense distance graphs
• Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• Faster Approximate Diameter and Distance Oracles in Planar Graphs
• scientific article; zbMATH DE number 7236428 (Why is no real title available?)
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• A story of diameter, radius, and (almost) Helly property
• _i-metric graphs: radius, diameter and all eccentricities
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Obstructions to faster diameter computation: asteroidal sets
• Almost optimal exact distance oracles for planar graphs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs

This page was built for publication: Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607914)