Dilation (graph theory)

The dilation of a Euclidean graph G = (V, E) is a measure of how much detour has to be accepted when going through the graph, compared to the direct Euclidean route. It is defined as the ratio of the distance in the graph to the distance in . ${\displaystyle \mathbb {R} ^{d}}$

definition

The dilation of two points and in a Euclidean graph is calculated from the costs of the shortest path d _min ( a , b ) from a to b , divided by the Euclidean distance : ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle |ab|}$

${\displaystyle \Delta (a,b)={\frac {d_{\mathrm {min} }(a,b)}{|ab|}}\,.}$

The dilation of the graph G is the maximum dilation of all pairs of points in V :

${\displaystyle \Delta (V)=\max _{a,b\in V}\Delta (a,b)\,.}$

literature

• Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein: The Geometric Dilation of Finite Point Sets . In: Algorithmica . 44, No. 2, 2006, pp. 137-149. doi : 10.1007 / s00453-005-1203-9 .