The plane-width of graphs

DOI10.1002/JGT.20554MaRDI QIDQ3096959zbMATH OpenOpenAlexFDO

Authors Marcin Kamiński, Paul Medvedev, Martin Milanič

Publication date 15 November 2011

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numbercircular chromatic numberpacking non-overlapping unit discsplane-widthrealization of a graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Euclidean analytic geometry (51N20)

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. We also investigate how plane-width behaves under various operations, such as homomorphism, disjoint union, complement, and the Cartesian product.

Recommendations

• On the plane-width of graphs
• On the path-width of planar graphs
• On the tree-width of planar graphs
• Pathwidth of planar and line graphs
• Asymptotic dimension of planes and planar graphs
• On some plane graphs and their metric dimension
• Diameter bounds for planar graphs
• scientific article; zbMATH DE number 1019602
• scientific article; zbMATH DE number 830027

Cites work

• A counterexample to Borsuk’s conjecture
• Circular chromatic number: A survey
• Covering a Three-Dimensional set with Sets of Smaller Diameter
• Dense packings of congruent circles in a circle
• Distinct distances in graph drawings
• Geometrical Extrema Suggested by a Lemma of Besicovitch
• Graph Theory and Probability
• Minimal diameter of certain sets in the plane
• New sets with large Borsuk numbers
• On extremal finite packings
• Realizability of graphs
• Small universal covers for sets of unit diameter
• Star chromatic number
• The chromatic number of random graphs
• The minimum diameter octagon with unit-length sides: Vincze's wife's octagon is suboptimal

Cited in

(7)

• Packing an equilateral polygon in a thin strip
• Dilation coefficient, plane-width, and resolution coefficient of graphs
• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
• Face-width of embedded graphs
• On the plane-width of graphs
• A note on planar graphs with large width parameters and small grid-minors
• Looseness of plane graphs

This page was built for publication: The plane-width of graphs

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