The Dilation Coefficient of Complete Graphs

Abstract

The dilation coefficient of a graph representation is defined as the quotient of the longest and the shortest edge representation. The minimum of the dilation coefficients over all planar representations of a graph G is called the dilation coefficient of the graph G. The dilation coefficient of different planar representations of complete graphs is considered and upper and lower bounds for the dilation coefficients of complete graphs are given. Two iterative graph-drawing algorithms that try to minimize the dilation coefficient of a given graph are given. The calculated upper bounds for the dilation coefficients of complete graphs are compared to the values obtained by the graph-drawing algorithms. [PUBLICATION ABSTRACT]