Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
1  
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
2  
@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
add comment

2 Answers 2

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.

share|improve this answer
    
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! –  Joseph O'Rourke May 25 '12 at 18:11
add comment

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)

share|improve this answer
    
Thanks, Igor, I did not know of the zeolite connection! –  Joseph O'Rourke May 25 '12 at 17:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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