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

https://hrcak.srce.hr/45617

Datum izdavanja:

20.12.2009.

Posjeta: 1.947 *