Geometry Lab [German] [Sitemap] [About geometrylab.de]
Home > Computational Geometry > Dilation > Graph-theoretic dilation of a graph

Graph-theoretic dilation of a graph

 

Introduction and definitions

The dilation of a graph specifies how much greater the shortest-path distance of two points of the graph over their euclidean distance can be. If C(p, q) denotes the shortest-path distance of two points p and q of a graph G = (V, E) and |pq| their euclidean distance, then the detour of p and q is defined as

detour(p, q) = C(p, q) / |pq|.
If we only consider the vertices of G, we get the graph-theoretic dilation
S(G) = max {detour(p, q); (p, q in V) & (p != q)}

Applet

[Applet cannot be started]
The applet GraphDilation (should start automatically) calculates the graph-theoretic dilation for a graph G=(V,E). Using Floyd's algorithm for determining all distances of the shortest paths for each pair of vertices, it has a running time in O(|V|3).

The current value of dilation is shown below the editing area. Each pair of vertices with a maximum value of dilation is connected by a green line segment for indication.

References

[1] David Eppstein. Spanning trees and spanners. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 425-461, Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.

[2] Tim Komorowski. Berechnung der graphentheoretischen Dilation. Diplomarbeit, Universität Bonn. 2004.

 

© University of Bonn, Computer Science I - - Last modified 09-02-2009 10:32