Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time

Research output: Working paperResearch

2025 Downloads (Pure)

Abstract

We solve three open problems: the existence of subquadratic time algorithms for computing the Wiener index (sum of APSP distances) and the diameter (maximum distance between any vertex pair) of a planar graph with non-negative edge weights and the stretch factor of a plane geometric graph (maximum over all pairs of distinct vertices of the ratio between the graph distance and the Euclidean distance between the two vertices). More specifically, we show that the Wiener index and diameter can be found in O(n^2*(log log n)^4/log n) worst-case time and that the stretch factor can be found in O(n^2*(log log n)^4/log n) expected time, where n is the number of vertices. We also show how to compute the Wiener index and diameter of an unweighted n-vertex subgraph-closed n^{0.5}-separable graph in O(n^2*log log n/log n) worst-case time and with O(n) space.
Original languageEnglish
Place of PublicationKøbenhavn
PublisherDepartment of Computer Science, University of Copenhagen
Number of pages30
Publication statusPublished - 2008

Cite this