The plane-width of graphs
Marcin Kamiński, Paul Medvedev, Martin Milanič · Journal of Graph Theory · 2011
Map the vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least unit distance apart. The plane-width of a graph is the minimum diameter of the image of its vertex set over all such mappings. We establish a relation between the plane-width of a graph and its chromatic number. We also connect it to other well-known areas, including the circular chromatic number and the problem of packing unit discs in the plane. © 2011 Wiley Periodicals, Inc. J Graph Theory 68: 229-245, 2011