# Touching-tetrahedra graphs

Have the graphs representable by touching tetrahedra been explored?

Let $\cal T$ be a collection of tetrahedra in $\mathbb{R}^3$ with pairwise disjoint interiors. Define a graph $G_{\cal T}$ to have a node for each tetrahedron in $\cal T$, and an arc between $T_1$ and $T_2$ if those two tetrahedra share one or more boundary points: $T_1 \cap T_2 \neq \varnothing$.

[Added] I neglected to add the significant qualification (of most interest to me) that each arc of $G_{\cal T}$ should be able to be associated with a unique point. My oversight only became clear with Aaron's example. Apologies! Of course one can make many definitions (such as Igor's variation), and all are of interest.

Which graphs $G$ are equal to $G_{\cal T}$ for some $\cal T$?

For example, $K_6$ is a touching-tetrahedra graph: In contrast, responses to an earlier MO question, "Extensions of the Koebe–Andreev–Thurston theorem to sphere packing?" showed that $K_6$ is not a ball-touching graph.

I know triangle-touching graphs in $\mathbb{R}^2$ have been studied, often called triangle contact representations, e.g., the recent paper by Gonçalves, Lévêque, and Pinlou, "Triangle Contact Representations and Duality." But I haven't found literature on the generalization to tetrahedra.

I would be interested in any pointers to the literature, or classes of graphs that either are or are not touching-tetrahedra graphs. E.g., is $K_7$ a touching-tetrahedra graph? Thanks!

• Just a remark: The barycentric subdivision of every finite graph is realized this way (probably also true for locally finite graphs). Here I consider only graphs which are simplicial complexes. – Misha May 25 '12 at 14:01
• Is this significantly different than asking for the family of graphs that are contact graphs of arbitrary convex solids? – Yoav Kallus May 25 '12 at 18:24
• @Yoav: Good question! I don't know. – Joseph O'Rourke May 25 '12 at 18:37
• @Yoav Infinitely many convex solids can touch face-to-face, and this is realized by Voronoi diagrams from sequences of points on curves like the moment curve. See Erickson, J. Kim, S. "Arbitrarily large neighborly families of congruent symmetric 3-polytopes." for many references. – Douglas Zare May 25 '12 at 21:08

That is an impressive $K_6$ graphic but any complete graph can be realized in a less exciting manner: take $n$ thin triangles in the plane with a single common vertex. This shows that $K_n$ is a planar triangle contact graph and hence a tetrahedral contact graph. The paper you reference requires at most one shared point per pair of triangles. It goes on to study planar networks getting simultaneous triangle representations of the graph and planar dual with pleasing properties. Maybe more restrictions would lead to interesting questions. Graphs with no $3$-cycles might be a challenge.