Dilation coefficient, plane-width, and resolution coefficient of graphs

DOI10.1007/S00605-013-0482-5MaRDI QIDQ1950340zbMATH OpenOpenAlexFDO

Authors Martin Milanič, Tomaž Pisanski, Arjana Žitnik

Publication date 13 May 2013

Published in Monatshefte für Mathematik (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1001.0330

zbMATH Keywords

bandwidthchromatic numbercircular chromatic numberdilation coefficientgraph drawinggraph representationplane-widthresolution coefficient

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: In this note we study and compare three graph invariants 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. We show that graphs with large dilation coefficient or plane-width have a vertex with large valence but there exist cubic graphs with arbitrarily large resolution coefficient. Surprisingly enough, the one-dimensional analogues of these three invariants allow us to revisit the three well known graph parameters: the circular chromatic number, the chromatic number, and the bandwidth. We also examine the connection between bounded resolution coefficient and minor-closed graph classes.

Recommendations

• The plane-width of graphs
• The geometric dilation of finite point sets
• On the plane-width of graphs
• Drawing Graphs in the Plane with High Resolution
• EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION

Cites work

• All generalized Petersen graphs are unit-distance graphs
• Automatic Domain Partitioning in Three Dimensions
• Circular chromatic number: A survey
• Geometrical Extrema Suggested by a Lemma of Besicovitch
• scientific article; zbMATH DE number 3963886 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• Minimal diameter of certain sets in the plane
• Models and approximation algorithms for channel assignment in radio networks
• On extremal finite packings
• On the plane-width of graphs
• Representing graphs and maps
• Star chromatic number
• The plane-width of graphs
• Unit disk graph recognition is NP-hard

This page was built for publication: Dilation coefficient, plane-width, and resolution coefficient of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1950340)