TY - GEN

T1 - Wiener index and Diameter of a Planar Graph in Subquadratic Time

AU - Wulff-Nilsen, Christian

N1 - Conference code: 25

PY - 2009

Y1 - 2009

N2 - Consider the problem of computing the sum of distances between each pair of vertices of an unweighted graph. This sum is also known as the Wiener index of the graph, a generalization of a definition given by H. Wiener in 1947. A molecular topological index is a value obtained from the graph structure of a molecule such that this value (hopefully) correlates with physical and/or chemical properties of the molecule. The Wiener index is perhaps the most studied molecular topological index with more than a thousand publications. It is open whether the Wiener index of a planar graph can be obtained in subquadratic time. In my talk, I will solve this open problem by exhibiting an O(n2 log log n / log n) time algorithm, where n is the size of the graph. A simple modification yields an algorithm with the same time bound that computes the diameter (maximum distance between any vertex pair) of a planar graph. I will also sketch the main ideas involved in obtaining O(n2(log log n)4/log n) time algorithms for planar graphs with arbitrary non-negative edge weights.

AB - Consider the problem of computing the sum of distances between each pair of vertices of an unweighted graph. This sum is also known as the Wiener index of the graph, a generalization of a definition given by H. Wiener in 1947. A molecular topological index is a value obtained from the graph structure of a molecule such that this value (hopefully) correlates with physical and/or chemical properties of the molecule. The Wiener index is perhaps the most studied molecular topological index with more than a thousand publications. It is open whether the Wiener index of a planar graph can be obtained in subquadratic time. In my talk, I will solve this open problem by exhibiting an O(n2 log log n / log n) time algorithm, where n is the size of the graph. A simple modification yields an algorithm with the same time bound that computes the diameter (maximum distance between any vertex pair) of a planar graph. I will also sketch the main ideas involved in obtaining O(n2(log log n)4/log n) time algorithms for planar graphs with arbitrary non-negative edge weights.

M3 - Article in proceedings

SP - 25

EP - 28

BT - Proceedings of the 25th European Workshop on Computational Geometry (EuroGC´09)

Y2 - 16 March 2009 through 18 March 2009

ER -