The graphs behind Reuleaux polyhedra

• Published in 2019
• Added on 2019-05-09

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

• http://arxiv.org/abs/1904.12761v1
• http://arxiv.org/pdf/1904.12761v1

Other information

BibTeX entry

@article{ThegraphsbehindReuleauxpolyhedra,
	key = {ThegraphsbehindReuleauxpolyhedra},
	type = {article},
	title = {The graphs behind Reuleaux polyhedra},
	author = {Luis Montejano and Eric Pauli and Miguel Raggi and Edgardo Rold{\'{a}}n-Pensado},
	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.},
	comment = {},
	date_added = {2019-05-09},
	date_published = {2019-05-03},
	urls = {http://arxiv.org/abs/1904.12761v1,http://arxiv.org/pdf/1904.12761v1},
	collections = {Geometry},
	url = {http://arxiv.org/abs/1904.12761v1 http://arxiv.org/pdf/1904.12761v1},
	year = 2019,
	urldate = {2019-05-09},
	archivePrefix = {arXiv},
	eprint = {1904.12761},
	primaryClass = {cs.CG}
}