Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Unit distance graph
Summary
In mathematics, 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 whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.
An unsolved problem of Paul Erdős asks how many edges a unit distance graph on vertices can have. The best known lower bound is slightly above linear in —far from the upper bound, proportional to . The number of colors required to color unit distance graphs is also unknown (the Hadwiger–Nelson problem): some unit distance graphs require five colors, and every unit distance graph can be colored with seven colors. For every algebraic number there is a unit distance graph with two vertices that must be that distance apart. According to the Beckman–Quarles theorem, the only plane transformations that preserve all unit distance graphs are the isometries.
It is possible to construct a unit distance graph efficiently, given its points. Finding all unit distances has applications in pattern matching, where it can be a first step in finding congruent copies of larger patterns. However, determining whether a given graph can be represented as a unit distance graph is NP-hard, and more specifically complete for the existential theory of the reals.
The unit distance graph for a set of points in the plane is the undirected graph having those points as its vertices, with an edge between two vertices whenever their Euclidean distance is exactly one.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.