  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.
