# The graphs behind Reuleaux polyhedra

- Published in 2019
- Added on

In the collection

This work is about graphs arising from Reuleaux polyhedra. Such graphs must necessarily be planar, $3$-connected and strongly self-dual. We study the question of when these conditions are sufficient. If $G$ is any such a graph with isomorphism $\tau : G \to G^*$ (where $G^*$ is the unique dual graph), a metric mapping is a map $\eta : V(G) \to \mathbb R^3$ such that the diameter of $\eta(G)$ is $1$ and for every pair of vertices $(u,v)$ such that $u\in \tau(v)$ we have dist$(\eta(u),\eta(v)) = 1$. If $\eta$ is injective, it is called a metric embedding. Note that a metric embedding gives rise to a Reuleaux Polyhedra. Our contributions are twofold: Firstly, we prove that any planar, $3$-connected, strongly self-dual graph has a metric mapping by proving that the chromatic number of the diameter graph (whose vertices are $V(G)$ and whose edges are pairs $(u,v)$ such that $u\in \tau(v)$) is at most $4$, which means there exists a metric mapping to the tetrahedron. Furthermore, we use the Lov\'asz neighborhood-complex theorem in algebraic topology to prove that the chromatic number of the diameter graph is exactly $4$. Secondly, we develop algorithms that allow us to obtain every such graph with up to $14$ vertices. Furthermore, we numerically construct metric embeddings for every such graph. From the theorem and this computational evidence we conjecture that every such graph is realizable as a Reuleaux polyhedron in $\mathbb R^3$. In previous work the first and last authors described a method to construct a constant-width body from a Reuleaux polyhedron. So in essence, we also construct hundreds of new examples of constant-width bodies. This is related to a problem of V\'azsonyi, and also to a problem of Blaschke-Lebesgue.

## Links

### BibTeX entry

@article{ThegraphsbehindReuleauxpolyhedra, title = {The graphs behind Reuleaux polyhedra}, abstract = {This work is about graphs arising from Reuleaux polyhedra. Such graphs must necessarily be planar, {\$}3{\$}-connected and strongly self-dual. We study the question of when these conditions are sufficient. If {\$}G{\$} is any such a graph with isomorphism {\$}\tau : G \to G^*{\$} (where {\$}G^*{\$} is the unique dual graph), a metric mapping is a map {\$}\eta : V(G) \to \mathbb R^3{\$} such that the diameter of {\$}\eta(G){\$} is {\$}1{\$} and for every pair of vertices {\$}(u,v){\$} such that {\$}u\in \tau(v){\$} we have dist{\$}(\eta(u),\eta(v)) = 1{\$}. If {\$}\eta{\$} is injective, it is called a metric embedding. Note that a metric embedding gives rise to a Reuleaux Polyhedra. Our contributions are twofold: Firstly, we prove that any planar, {\$}3{\$}-connected, strongly self-dual graph has a metric mapping by proving that the chromatic number of the diameter graph (whose vertices are {\$}V(G){\$} and whose edges are pairs {\$}(u,v){\$} such that {\$}u\in \tau(v){\$}) is at most {\$}4{\$}, which means there exists a metric mapping to the tetrahedron. Furthermore, we use the Lov\'asz neighborhood-complex theorem in algebraic topology to prove that the chromatic number of the diameter graph is exactly {\$}4{\$}. Secondly, we develop algorithms that allow us to obtain every such graph with up to {\$}14{\$} vertices. Furthermore, we numerically construct metric embeddings for every such graph. From the theorem and this computational evidence we conjecture that every such graph is realizable as a Reuleaux polyhedron in {\$}\mathbb R^3{\$}. In previous work the first and last authors described a method to construct a constant-width body from a Reuleaux polyhedron. So in essence, we also construct hundreds of new examples of constant-width bodies. This is related to a problem of V\'azsonyi, and also to a problem of Blaschke-Lebesgue.}, url = {http://arxiv.org/abs/1904.12761v1 http://arxiv.org/pdf/1904.12761v1}, year = 2019, author = {Luis Montejano and Eric Pauli and Miguel Raggi and Edgardo Rold{\'{a}}n-Pensado}, comment = {}, urldate = {2019-05-09}, archivePrefix = {arXiv}, eprint = {1904.12761}, primaryClass = {cs.CG}, collections = {Geometry} }