Unit distance graph

The Petersen graph is a graph of unit distances — it can be drawn on a plane so that each edge has a unit length.

In graph theory, a graph of unit distances is a graph formed by points on the Euclidean plane, and two vertices are connected by an edge if the distance between them is exactly one. The edges of the unit distance graph sometimes intersect, so they are not always planar . The graph of unit distances without intersections is called the match graph .

The Nelson – Erdos – Hadwiger problem concerns the chromatic number of unit distance graphs. It is known that unit distance graphs exist that require 5 colors for proper coloring and that all such graphs can be colored in no more than 7 colors. Another important open problem concerning unit distance graphs asks how many edges such a graph can have in relation to the number of vertices .

Examples

The hypercube graph Q _{4 is the} unit distance graph.

The following graphs are unit distance graphs:

any cycle ;
any grate ;
any graph of a hypercube ;
any star ;
Count of Petersen ;
Earl of Howwood ( Gerbracht 2009 );
Wheel W ₇ ;
Moser spindle , smallest unit distance graph with chromatic number 4.

Subgraphs of unit distance graphs

A drawing with unit distances of the Mobius – Cantor graph , in which some non-adjacent edges are also at a distance of one.

Some authors define the unit distance graph as a graph that can be embedded in a plane so that any two adjacent vertices must be at a distance of one, but not necessarily vertices that are at a distance of one must be adjacent. For example, the Mobius-Cantor graph has a graphical representation of this kind.

According to this definition, all generalized Petersen graphs are unit distance graphs ( Žitnik, Horvat, Pisanski 2010 ). To distinguish between these two definitions, graphs for which any two vertices located at a distance of unity are connected by an edge, we will call strict graphs of unit distances ( Gervacio, Lim, Maehara 2008 ).

Wheel W ₇ with a remote spoke as an example of a graph of unit distances, but not a strict graph of unit distances

The graph formed by removing one spoke from the wheel W ₇ is a subgraph of unit distances, but not a strict graph of unit distances ( Soifer 2008 , p. 94).

Counting unit distances

Unsolved problems in mathematics : How many unit distances can be in a set of n points?

Erdős ( 1946 ) proposed the problem of estimating, in a set of n points, the number of pairs located at a distance of unity. In terms of graph theory, the question is about estimating the graph density of unit distances.

The hypercube graph gives the lower bound for the number of unit distances proportional to $n\log n.$ ${\ displaystyle n \ log n.}$ Looking at the points of a square lattice with a carefully chosen distance, Erdös found an improved lower bound

n^{1+c/\log \log n},

{\ displaystyle n ^ {1 + c / \ log \ log n},}

and offered a bonus of $ 500 for figuring out whether the maximum number of unit distances is expressed by a function of the same kind ( Kuperberg 1992 ). The best known boundary, according to Spencer, Semeredi, and Trotter ( Spencer, Szemerédi, Trotter 1984 ), is proportional

n^{4/3};

{\ displaystyle n ^ {4/3};}

.

This boundary can be considered as the number of hits of points on unit circles, and it is closely related to the Szemeredi-Trotter theorem on the incidence of points and lines.

Representation of Algebraic Numbers and the Beckman-Quarles Theorem

For any algebraic number A, we can find the unit distance graph G in which some pairs of vertices are at distance A in all representations with unit distances G ( Maehara 1991 ) ( Maehara 1992 ). This result implies a finite version —for any two points p and q located at a distance A , there exists a finite unit graph of unit distances containing p and q such that any plane transformation preserving unit distances in this graph keeps the distance between p and q ( Tyszka 2000 ). The complete Beckman-Quarles theorem states that any transformation of a Euclidean plane (or a space of greater dimension) preserving distances must be a congruence . Thus, for infinite graphs of unit distances whose vertices are the entire plane, any must be an isometry ( Beckman, Quarles 1953 ).

Generalization to large dimensions

The definition of the unit distance graph can be naturally generalized to any dimension of Euclidean space . Any graph can be embedded as a set of points in a space of a sufficiently high dimension. Maehara and Rödl ( 1990 ) showed that the dimension required for embedding a graph can be limited to twice the maximum degree.

The dimension required for embedding the graph at which all the edges will have a unit length, and the dimension of embedding at which the edges will connect exactly the points between which the distance is one, can differ significantly. A crown with 2 n vertices can be embedded in four-dimensional space so that all edges have a unit length, but at least dimension n - 2 is required to insert so that there are no pairs of vertices located at a distance of one not connected by an edge ( Erdős , Simonovits 1980 ).

Computational complexity

It is an NP-hard task , more precisely complete for the , to check whether a given graph is a unit distance graph or a strict unit distance graph ( Schaefer 2013 ).

Notes

FS Beckman, DA, Jr. Quarles On isometries of Euclidean spaces // Proceedings of the American Mathematical Society. - 1953. - T. 4 . - S. 810-815 .
Paul Erdős. On sets of distances of n points. - American Mathematical Monthly . - The American Mathematical Monthly, 1946. - T. 53. - S. 248-250. - DOI : 10.2307 / 2305092 . .
Paul Erdős, Miklós Simonovits. On the chromatic number of geometric graphs // Ars Combinatoria. - 1980 .-- T. 9 . - S. 229-246 . As cited in Soifer, 2008 , p. 97.
Eberhard H.-A. Gerbracht. Eleven unit distance embeddings of the Heawood graph. - 2009 .-- arXiv : 0912.5395 . .
Severino V. Gervacio, Yvette F. Lim, Hiroshi Maehara. Planar unit-distance graphs having planar unit-distance complement // Discrete Mathematics. - 2008. - T. 308 , no. 10 . - S. 1973-1984 . - DOI : 10.1016 / j.disc.2007.04.04.050 . .
Greg Kuperberg. The Erdos kitty: At least $ 9050 in prizes! . - 1992. Archived on September 29, 2006.
Hiroshi Maehara. Distances in a rigid unit-distance graph in the plane // Discrete Applied Mathematics. - 1991 .-- T. 31 , no. 2 . - S. 193-200 . - DOI : 10.1016 / 0166-218X (91) 90070-D . .
Hiroshi Maehara. Extending a flexible unit-bar framework to a rigid one // Discrete Mathematics. - 1992. - T. 108 , no. 1-3 . - S. 167-174 . - DOI : 10.1016 / 0012-365X (92) 90671-2 . .
Hiroshi Maehara, Vojtech Rödl. On the dimension to represent a graph by a unit distance graph // Graphs and Combinatorics. - 1990. - T. 6 , no. 4 . - S. 365-367 . - DOI : 10.1007 / BF01787703 . .
Marcus Schaefer. Thirty Essays on Geometric Graph Theory / János Pach. - Springer, 2013 .-- S. 461-482. - DOI : 10.1007 / 978-1-4614-0110-0_24 . .
Alexander Soifer. The Mathematical Coloring Book. - Springer-Verlag, 2008 .-- ISBN 978-0-387-74640-1 .
Joel Spencer, Endre Szemerédi, William T. Trotter. Graph Theory and Combinatorics. - Academic Press, 1984. - S. 293-308.
Apoloniusz Tyszka. Discrete versions of the Beckman-Quarles theorem // Aequationes Mathematicae. - 2000. - T. 59 , no. 1-2 . - S. 124-133 . - DOI : 10.1007 / PL00000119 . .
Arjana Žitnik, Boris Horvat, Tomaž Pisanski. All generalized Petersen graphs are unit-distance graphs . - 2010 .-- T. 1109 .

Links

Suresh Venkatasubramanian. Problem 39: Distances among Point Sets in R ² and R ³ // The Open Problems Project. Archived August 30, 2006.
Weisstein, Eric W. Unit-Distance Graph on Wolfram MathWorld .