Unit Distance Graphs

Consider the plane as a metric space with a distance function derived from a vector-norm. A unit distance graph is then a set of points (the vertices) in the plane together with a set of lines (the edges), each line connecting two vertices whose distance is equal to 1.

We try to colour the vertices such that two neighbours (i.e. two vertices connected by en edge) always receive different colours.

The necessary number of colours depends on the metric.

In the papers I have now removed, I was mainly interested in an accurate description of the quadrangular and hexagonal cases.

In the remaining paper I show that certain graphs (for instance K_5) cannot be induced subgraphs of a unit distance graph in a polygonal geometry.


  1. Non unit distance graphs