Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414863 | Computational Geometry | 2009 | 10 Pages |
We show that, for any fixed constant k⩾3, the sum of the distances between all pairs of vertices of an abstract graph with n vertices and treewidth at most k can be computed in O(nlogk−1n) time.We also show that, for any fixed constant k⩾2, the dilation of a geometric graph (i.e., a graph drawn in the plane with straight-line segments) with n vertices and treewidth at most k can be computed in O(nlogk+1n) expected time. The dilation (or stretch-factor) of a geometric graph is defined as the largest ratio, taken over all pairs of vertices, between the distance measured along the graph and the Euclidean distance.The algorithms for both problems are based on the same principle: data structures for orthogonal range searching in bounded dimension provide a compact representation of distances in abstract graphs of bounded treewidth.