Approximating the Diameter of Planar Graphs in Near Linear Time

DOI10.1145/2764910MaRDI QIDQ4962209zbMATH OpenOpenAlexFDO

Authors Oren Weimann, Raphael Yuster

Publication date 30 October 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2764910

zbMATH Keywords

all-pairs shortest pathsdiameterdistance oraclesplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Approximating the diameter of planar graphs in near linear time
• Faster approximate diameter and distance oracles in planar graphs
• Faster Approximate Diameter and Distance Oracles in Planar Graphs
• Diameter bounds for planar graphs
• Linear-time graph distance and diameter approximation
• Linear-time algorithms for problems on planar graphs with fixed disk dimension
• Better approximation algorithms for the graph diameter
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs

Cited in

(26)

• Diameter and treewidth in minor-closed graph families
• Faster approximate diameter and distance oracles in planar graphs
• On Approximating the d-Girth of a Graph
• Computing the Girth of a Planar Graph in O(n logn) Time
• Complexity of approximating the oriented diameter of chordal graphs
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• Fast approximation of eccentricities and distances in hyperbolic graphs
• A strongly-uniform slicewise polynomial-time algorithm for the embedded planar diameter improvement problem
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• Faster Approximate Diameter and Distance Oracles in Planar Graphs
• scientific article; zbMATH DE number 7236428 (Why is no real title available?)
• Succinct enumeration of distant vertex pairs
• Planar diameter via metric compression
• Fast and Simple Approximation of the Diameter and Radius of a Graph
• Approximating the diameter of planar graphs in near linear time
• scientific article; zbMATH DE number 5050599 (Why is no real title available?)
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Parameterized complexity of diameter
• Diameter bounds for planar graphs
• $$\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities
• _i-metric graphs: radius, diameter and all eccentricities
• The complexity of diameter on H-free graphs
• The complexity of diameter on \(H\)-free graphs
• Improved outerplanarity bounds for planar graphs
• Going beyond surfaces in diameter approximation

This page was built for publication: Approximating the Diameter of Planar Graphs in Near Linear Time

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