Croatica Chemica Acta, Vol. 82 No. 4, 2009.
Izvorni znanstveni članak
The Dilation Coefficient of Complete Graphs
Boris Horvat
; IMFM, University of Ljubljana, Jadranska 19, Ljubljana, Slovenia
Tomaž Pisanski
; IMFM, University of Ljubljana, Jadranska 19, Ljubljana, and University of Primorska, Koper, Slovenia
Arjana Žitnik
; IMFM, University of Ljubljana, Jadranska 19, Ljubljana, Slovenia
Sažetak
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.
Ključne riječi
dilation coefficient; graph representation; energy of a representation; algorithm; circular representation; complete graph; circular packing
Hrčak ID:
45617
URI
Datum izdavanja:
20.12.2009.
Posjeta: 1.989 *