5
$\begingroup$

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
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!

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Misha
    May 25, 2012 at 14:01
  • $\begingroup$ Is this significantly different than asking for the family of graphs that are contact graphs of arbitrary convex solids? $\endgroup$ May 25, 2012 at 18:24
  • $\begingroup$ @Yoav: Good question! I don't know. $\endgroup$ May 25, 2012 at 18:37
  • 2
    $\begingroup$ @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. $\endgroup$ May 25, 2012 at 21:08

2 Answers 2

3
$\begingroup$

Not an answer, but if you require your tetrahedra to be regular, and allow them to only intersect at vertices, you get a central problem in physical chemistry (since such graphs correspond, loosely speaking, to Zeolites. For more, google "zeolite, Treacy, Rivin" (you won't find an answer, just more context)

$\endgroup$
1
  • $\begingroup$ Thanks, Igor, I did not know of the zeolite connection! $\endgroup$ May 25, 2012 at 17:56
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Ah, I see I was implicitly requiring each arc of the graph to be mediated by a unique point not employed by any other arc. Not part of the definition I framed. Thanks, Aaron! $\endgroup$ May 25, 2012 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.