Geometric Realizations with Strong Self-Duality Part II: Diameter Graphs, Reuleaux Polyhedra, and Thrackles
Abstract
In this paper we construct new examples of diameter graphs and Reuleaux polyhedra in ℝ3, obtaining a full characterization of their combinatorial structure. For a finite set of points X⊂ℝd, its diameter graph is the graph on vertex set X where pairs forming a diameter pair are connected by an edge. Grünbaum, Heppes and Straszewicz independently proved that the diameter graph of X⊂ ℝ3 has at most 2|X|−2 edges, answering a question of Vázsonyi. Their proof relied on ball polytopes. The ball polytope ℬ(X) is the intersection of the unit balls centered at the points of X. We call a ball polytope a Reuleaux polyhedron if the centers form a family with 2|X|−2 diameter pairs. Kupitz, Martini and Perles showed that the skeleton of a Reuleaux polyhedron must be a 2-connected strongly involutive self-dual graph. They conjectured that in the simple 3-connected case this is also sufficient. We not only confirm this conjecture, but we show that any 2-connected (not necessarily simple) strongly involutive self-dual graph arises as the skeleton of a Reuleaux polyhedron. To construct the new Reuleaux polyhedra we construct new diameter graphs. It was known that any 3-dimensional diameter graph is a subgraph of a non-bipartite quadrangulation of the projective plane. We show that the reverse holds. That is, for any such graph we construct a diameter realization. This also confirms and strengthens a conjecture of Montejano, Pauli, Raggi, Roldán-Pensado on metric embeddings of strongly involutive self-dual graphs. The construction relies on ideas from rigidity theory. We also discuss a number of applications of these results, such as the construction of bodies of constant width and connections to Steinitz's theorem and Borsuk's conjecture.
Related
- A new family of constant width bodies obtained from Reuleaux polyhedra
- Geometric realizations of Brauer classes on K3 surfaces from hyperkähler contractions
- Geometric Realizations of Capability Spaces of Large Models and Zigzag Persistent Homology
- A priori bounds for geodesic diameter. Part III. A Sobolev–Poincaré inequality and applications to a variety of geometric variational problems
- Geometric Realizations with Strong Self-Duality Part I: Non-Bipartite Quadrangulations of the Projective Plane and Strongly Involutive Self-Dual Graphs
BibTeX
@misc{damasdi2026geometric,
title = {{Geometric Realizations with Strong Self-Duality Part II: Diameter Graphs, Reuleaux Polyhedra, and Thrackles}},
author = {Gábor Damásdi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06340},
eprint = {2610.06340},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06340},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Geometric Realizations with Strong Self-Duality Part II: Diameter Graphs, Reuleaux Polyhedra, and Thrackles
AU - Gábor Damásdi
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06340
UR - https://arxiv.org/abs/2610.06340
AB - In this paper we construct new examples of diameter graphs and Reuleaux polyhedra in ℝ^3, obtaining a full characterization of their combinatorial structure. For a finite set of points X⊂ℝ^d, its diameter graph is the graph on vertex set X where pairs forming a diameter pair are connected by an edge. Grünbaum, Heppes and Straszewicz independently proved that the diameter graph of X⊂ ℝ^3 has at most 2|X|−2 edges, answering a question of Vázsonyi. Their proof relied on ball polytopes. The ball polytope ℬ(X) is the intersection of the unit balls centered at the points of X. We call a ball polytope a Reuleaux polyhedron if the centers form a family with 2|X|−2 diameter pairs. Kupitz, Martini and Perles showed that the skeleton of a Reuleaux polyhedron must be a 2-connected strongly involutive self-dual graph. They conjectured that in the simple 3-connected case this is also sufficient. We not only confirm this conjecture, but we show that any 2-connected (not necessarily simple) strongly involutive self-dual graph arises as the skeleton of a Reuleaux polyhedron. To construct the new Reuleaux polyhedra we construct new diameter graphs. It was known that any 3-dimensional diameter graph is a subgraph of a non-bipartite quadrangulation of the projective plane. We show that the reverse holds. That is, for any such graph we construct a diameter realization. This also confirms and strengthens a conjecture of Montejano, Pauli, Raggi, Roldán-Pensado on metric embeddings of strongly involutive self-dual graphs. The construction relies on ideas from rigidity theory. We also discuss a number of applications of these results, such as the construction of bodies of constant width and connections to Steinitz's theorem and Borsuk's conjecture.
ER -