Unit distance graph

Unit distance graph

In mathematics, and particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one. Edges of unit distance graphs sometimes cross each other, so they are not always planar.

The Hadwiger–Nelson problem concerns the chromatic number of unit distance graphs. It is known that there exist unit distance graphs requiring four colors in any proper coloring, and that all such graphs can be colored with at most seven colors.

For any algebraic number "A", it is possible to find a unit distance graph "G" in which some pair of vertices are at distance "A" in any unit distance representation of "G" (Maehara 1991).

Examples

The following graphs are unit distance graphs:
* Any cycle graph
* Any grid graph
* Any hypercube graph
* The Petersen graph
* The wheel graph "W"7

Counting unit distances

Erdős (1946) posed the problem of estimating how many pairs of points in a set of "n" points could be at unit distance from each other. In graph theoretic terms, how dense can a unit distance graph be?

The hypercube graph provides a lower bound on the number of unit distances proportional to nlog n. By considering points in a square grid with carefully chosen spacing, Erdős found an improved lower bound of the form

:n^{1+frac{c}{loglog n,

and offered a prize of $500 for determining whether or not the maximum number of unit distances can also be upper bounded by a function of this form (Kuperberg 1992). The best known upper bound for this problem, due to Spencer, Szemerédi, and Trotter (1984), is proportional to

:n^{frac43};this bound can also be viewed as counting incidences between points and unit circles, and is closely related to the Szemerédi–Trotter theorem on incidences between points and lines.

Generalization to higher dimensions

The definition of a unit distance graph may naturally be generalized to any higher dimensional Euclidean space.Any graph may be embedded as a set of points in a sufficiently high dimension; Maehara and Rödl (1990) show that the dimension necessary to embed a graph in this way may be bounded by twice its maximum degree.

See also

* Unit disk graph

References

* cite journal
author = Erdős, Paul
authorlink = Paul Erdős
title = On sets of distances of "n" points
journal = American Mathematical Monthly
volume = 53
year = 1946
pages = 248–250
doi = 10.2307/2305092

* cite web
author = Kuperberg, Greg
year = 1992
title = The Erdos kitty: At least $9050 in prizes!
work = Posting to usenet groups rec.puzzles and sci.math
url = http://www.math.niu.edu/~rusin/known-math/93_back/prizes.erd

* cite journal
journal = Discrete Applied Mathematics
volume = 31
issue = 2
year = 1991
pages = 193–200
doi = 10.1016/0166-218X(91)90070-D
title = Distances in a rigid unit-distance graph in the plane
author = Maehara, Hiroshi

* cite journal
author = Maehara, Hiroshi; Rödl, Vojtech
title = On the dimension to represent a graph by a unit distance graph
journal = Graphs and Combinatorics
volume = 6
issue = 4
year = 1990
pages = 365–367
doi = 10.1007/BF01787703

* cite conference
author = Spencer, Joel; Szemerédi, Endre; Trotter, William T.
title = Unit distances in the Euclidean plane
booktitle = Graph Theory and Combinatorics
publisher = Academic Press
year = 1984
pages = 293–308

External links

* cite web
author = Venkatasubramanian, Suresh
title = Problem 39: Distances among Point Sets in R2 and R3
work = The Open Problems Project
url = http://maven.smith.edu/~orourke/TOPP/P39.html

*


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Unit disk graph — In geometric graph theory, a unit disk graph is the intersection graph of a family of unit circles in the Euclidean plane. That is, we form a vertex for each circle, and connect two vertices by an edge whenever the corresponding circles cross… …   Wikipedia

  • Distance (disambiguation) — Distance is a numerical description of how far apart objects are. Distance may also refer to: Distance (band), a late 1980s rock supergroup featuring Bernard Edwards and Tony Thompson The distance (boxing), a term for boxing in which a fight goes …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Unit disk — For other uses, see Disc (disambiguation). An open Euclidean unit disk In mathematics, the open unit disk (or disc) around P (where P is a given point in the plane), is the set of points whose distance from P is less than 1 …   Wikipedia

  • Einheitsdistanz-Graph — Der Petersen Graph ist ein Einheitsdistanz Graph: er kann so gezeichnet werden, dass jede Kante gleich lang ist. Ein Einheitsdistanz Graph ist ein geometrischer Graph, bei dem jede Kante gleich lang ist. Kanten eines Einheitsdistanz Graphen… …   Deutsch Wikipedia

  • Crown graph — Crown graphs with six, eight, and ten vertices. In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices ui and vi and with an edge from ui to vj whenever i ≠ j. The crown… …   Wikipedia

  • Nauru graph — The Nauru graph is Hamiltonian. Vertices 24 Edges 36 Radius 4 …   Wikipedia

  • Geometric graph theory — In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs. Notable geometric… …   Wikipedia

  • Möbius–Kantor graph — Named after August Ferdinand Möbius and S. Kantor Vertices 16 …   Wikipedia

  • De Bruijn–Erdős theorem (graph theory) — This article is about coloring infinite graphs. For the number of lines determined by a finite set of points, see De Bruijn–Erdős theorem (incidence geometry). In graph theory, the De Bruijn–Erdős theorem, proved by Nicolaas Govert de Bruijn and… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”