Skip to main content
3 of 4
replaced http://mathoverflow.net/ with https://mathoverflow.net/

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:
           TouchingTetrahedra http://cs.smith.edu/~orourke/MathOverflow/TouchingTetrahedra.jpg
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!

Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958