A diameter graph of a finite set of at least two points in Euclidean
space is the simple graph with vertex
set
in which two distinct vertices are adjacent iff their Euclidean distance
is the generalized diameter of
(Graham 1975, p. 166). The graph
diameter is a different quantity defined using graph
distance.
For the vertex set of a regular polygon with an odd number of sides, the diameter graph is the cycle
graph
.
For an even number
of sides, it is the graph
disjoint union of
copies of the complete graph
, joining opposite vertices.
Indeed, the longest chords advance
steps around the odd polygon
and
steps around the even polygon.
Diameter graphs record the distance constraints attained with equality in the biggest little polygon problem, where the polygon diameter is fixed and the area is maximized.