On the Plane-Width of Graphs

Marcin Kamiński; Paul Medvedev; Martin Milanič

doi:10.1016/j.endm.2009.07.107

On the Plane-Width of Graphs

Marcin Kamiński
, Paul Medvedev
, Martin Milanič

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

Map vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least a unit distance apart. The plane-width of a graph is the minimum diameter of the image of the vertex set over all such mappings. We establish a relation between the plane-width of a graph and its chromatic number, and connect it to other well-known areas, including the circular chromatic number and the problem of packing unit discs in the plane.

Original language	English (US)
Pages (from-to)	633-637
Number of pages	5
Journal	Electronic Notes in Discrete Mathematics
Volume	34
DOIs	https://doi.org/10.1016/j.endm.2009.07.107
State	Published - Aug 1 2009

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2009.07.107

Cite this

@article{28f679b1de894c4da412cfd3646e030c,

title = "On the Plane-Width of Graphs",

abstract = "Map vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least a unit distance apart. The plane-width of a graph is the minimum diameter of the image of the vertex set over all such mappings. We establish a relation between the plane-width of a graph and its chromatic number, and connect it to other well-known areas, including the circular chromatic number and the problem of packing unit discs in the plane.",

author = "Marcin Kami{\'n}ski and Paul Medvedev and Martin Milani{\v c}",

year = "2009",

month = aug,

day = "1",

doi = "10.1016/j.endm.2009.07.107",

language = "English (US)",

volume = "34",

pages = "633--637",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - On the Plane-Width of Graphs

AU - Kamiński, Marcin

AU - Medvedev, Paul

AU - Milanič, Martin

PY - 2009/8/1

Y1 - 2009/8/1

N2 - Map vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least a unit distance apart. The plane-width of a graph is the minimum diameter of the image of the vertex set over all such mappings. We establish a relation between the plane-width of a graph and its chromatic number, and connect it to other well-known areas, including the circular chromatic number and the problem of packing unit discs in the plane.

AB - Map vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least a unit distance apart. The plane-width of a graph is the minimum diameter of the image of the vertex set over all such mappings. We establish a relation between the plane-width of a graph and its chromatic number, and connect it to other well-known areas, including the circular chromatic number and the problem of packing unit discs in the plane.

UR - https://www.scopus.com/pages/publications/67651162013

UR - https://www.scopus.com/pages/publications/67651162013#tab=citedBy

U2 - 10.1016/j.endm.2009.07.107

DO - 10.1016/j.endm.2009.07.107

M3 - Article

AN - SCOPUS:67651162013

SN - 1571-0653

VL - 34

SP - 633

EP - 637

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

On the Plane-Width of Graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this