Dilation coefficient, plane-width, and resolution coefficient of graphs |
| |
Authors: | Martin Milanič Tomaž Pisanski Arjana Žitnik |
| |
Institution: | 1. University of Primorska, UP IAM, Muzejski trg 2, SI, 6000, Koper, Slovenia 2. University of Primorska, UP FAMNIT, Glagolja?ka 8, SI, 6000, Koper, Slovenia 3. University of Ljubljana, IMFM, Jadranska 19, 1111, Ljubljana, Slovenia
|
| |
Abstract: | In this paper we investigate the relations between three graph invariants that are related to the ‘compactness’ of graph drawing in the plane: the dilation coefficient, defined as the smallest possible quotient between the longest and the shortest edge length; the plane-width, which is the smallest possible quotient between the largest distance between any two points and the shortest length of an edge; and the resolution coefficient, the smallest possible quotient between the longest edge length and the smallest distance between any two points. These three invariants coincide for complete graphs. More specifically, we show that the plane-width and the dilation coefficient are equivalent graph parameters in the sense that they are bounded on the same sets of graphs, while bounded resolution coefficient implies bounded plane-width (or dilation coefficient) but not conversely. It is known that the one-dimensional analogues of the plane-width and the resolution coefficient are closely related to the chromatic number and the bandwidth respectively. We complete this picture by showing that a graph of one-dimensional dilation coefficient $d$ is exactly the same as a graph of circular chromatic number $d+1$ . Finally, we complement the result that a graph of resolution coefficient less than $\sqrt{2}$ is planar by constructing a family of graphs of resolution coefficient $\sqrt{2}$ not contained in any nontrivial minor-closed graph family. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|