3
$\begingroup$

Given a graph, along with a set describing which edges are connected to form faces, how could we determine whether it is embeddable in 3D Euclidean space, a.k.a $\Bbb R^3$? What formula applies here?

Assume faces can be curved in the same way that lines can be curved in a graph.

Imagine a soccer ball with a hole that cut out one polygon—in the same way, what I’m imagining doesn’t require the edges formed by the vertices of this soccer ball to all form faces.

I was reading about Euler’s formula for planar graphs, wherein v-e+f=c+1 (the number of vertices minus the number of edges plus the number of faces equals the number of connected components plus one).

However, the usage of faces doesn’t work here, because there are an infinite number of planes in $\Bbb R^3$, and the part of Euler’s proof that uses the number of faces increasing when a region becomes bound in by points doesn’t work here. Since nonplanar graphs can be embedded in $\Bbb R^3$, and the formula only applies to planar graphs, Euler’s formula can’t be the right first step.

This would probably be defined by a hypergraph, but I don’t know much about them.

Edit: Assume the new definition of “face” to be a set of three and only three edges. Any number of edges could technically be a face but only three are necessarily coplanar under shifts of the points. Faces with more edges can be subdivided into triangles.

I realized earlier that if there exists an edge on the structure that has only one face connected to it, a volume is not enclosed by that structure. I found the contrapositive of this, namely, that a volume is enclosed if, for all edges in the structure, each edge has a greater-than-one number of faces connected to it.

I also noticed that two volumes are enclosed (leaving three total when considering the “outside” region) when there exists an edge with three unique faces connected to it—assuming that the structure already satisfies the property of every edge having at least two unique faces connected to it. I don’t know how to prove this, but I can picture it.

Edit: Two views about the number of edges a face should have: I know that an edge on a graph is allowed to curve, so perhaps faces on these edged-volumes I’ve defined should be able to as well. However, edges on regular graphs only ever connect two vertices, so faces on these volumes should probably be restricted to possessing the minimum number of edges that a face can have.

Important Edit: Essentially, what I want to find is the simplest example of a set of surfaces connected at edges that cannot be embedded in a 3-dimensional Euclidean space without planes crossing.

$\endgroup$
4
  • 1
    $\begingroup$ It is probably impossible to give a general criterion to tell whether a structure that "could be" a geometric polyhedron actually can be realized geometrically. For example, en.wikipedia.org/wiki/Abstract_polytope offers the (grammatically questionable and uncited, but also true) "In general, only a restricted set of abstract polytopes of rank n may be realized faithfully in any given n-space. The characterization of this effect is an outstanding problem." $\endgroup$
    – JBL
    Dec 4, 2022 at 0:52
  • 1
    $\begingroup$ For example, it's not known whether there are any polyhedra other than the tetrahedron and the Császár polyhedron (en.wikipedia.org/wiki/Cs%C3%A1sz%C3%A1r_polyhedron) whose skeleton is a complete graph. $\endgroup$
    – JBL
    Dec 4, 2022 at 0:55
  • 1
    $\begingroup$ Try looking into Algebraic Topology, in-particular simplicial complex and simplicial homology. In wiki page, See topological definition of Euler's characteristic. en.wikipedia.org/wiki/… . Now try to visualize the graph embedding be made such that each face is a simplicial complex in 3D space. $\endgroup$
    – Balaji sb
    Dec 4, 2022 at 4:48
  • 2
    $\begingroup$ See also: en.wikipedia.org/wiki/CW_complex#Definition $\endgroup$
    – Balaji sb
    Dec 4, 2022 at 4:57

1 Answer 1

5
+25
$\begingroup$

I don't know an efficient algorithm in general, but your final paragraph just says that you are looking for a simple example of something non-embeddable. For this, I would use a triangulation of the projective plane.

You can achieve this with just $6$ vertices, which I'll call $\{ a,b,c,d,e,f \}$. The edges are the complete graph $K_6$ and the triangles are

abf, bcf, cdf, def, eaf, abd, bce, cda, deb, eac . 

I found a picture of this simplicial complex here.

enter image description here

I computed this by taking the $12$ vertices of an icosahedron (which is a triangulation of the sphere $S^2$) and labeling antipodal vertices with the same number. The $20$ triangles in the icosahedron get $10$ distinct labels, which are the labels listed above. So we get a triangulation of $S^2 / \langle \pm 1 \rangle$, which is to say, a triangulation of $\mathbb{RP}^2$.

If you aren't comfortable with projective planes and quotient spaces, you can see the structure of this example by looking at the first 5 triangles I've listed and the last 5. The first 5 triangles form a pentagonal disc, with boundary $abcde$ and $f$ in the center. The other 5 form a Mobius strip, with boundary $abcde$. So the point is that you can't sew the boundary of a disc to the boundary of a Mobius strip.


$6$ vertices are optimal. If we have any simplicial complex with $5$ (or fewer vertices), we can send the $4$ of the points to the vertices of a tetrahedron and the last point to the interior, join all edges with straight line segments and fill all faces with triangles, and this will have no self intersections.


I also found this old question, which says that the minimal triangulation of a Klein bottle has $8$ vertices.


Regarding algorithms: You could ask about linear embeddings, meaning that all edges must be sent to line segments and all faces to triangles, or you could ask about continuous embeddings. (There are also things like "piecewise linear", "piecewise smooth" or "smooth", but I think those should all be equivalent to continuous.)

  • For linear embeddings, this is a matter of solving finitely many polynomial inequalities in finitely many variables: Write the coordinates of each vertex as $v_i:=(x_i, y_i, z_i)$ and then write down an inequality saying that faces which are supposed to be disjoint don't cross. I think it should be enough to impose, for every face $(v_1, v_2, v_3)$, and every edge $(v_4, v_5)$, that the line segment doesn't cross the interior of the triangle. To do this, solve the linear equations $$\begin{bmatrix} x_1&x_2&x_3&-x_4&-x_5 \\ y_1&y_2&y_3&-y_4&-y_5 \\ z_1&z_2&z_3&-z_4&-z_5 \\ 1&1&1 & 0&0 \\ 0&0&0&1&1 \\ \end{bmatrix} \begin{bmatrix} p_1\\p_2\\p_3\\p_4\\p_5 \end{bmatrix} = \begin{bmatrix} 0\\0\\0\\1\\1 \end{bmatrix}$$ to find $(p_1, p_2, p_3, p_4, p_5)$ with $p_1 v_1 + p_2 v_2 + p_3 v_3 = p_4 v_4 + p_5 v_5$, and $p_1+p_2+p_3 = p_4+p_5 = 1$; then impose that the $p_i$ are not all positive. (You'll also want to impose that $v_i \neq v_j$ and that $(v_i, v_j, v_k)$ are not collinear for any face $(v_i, v_j, v_k)$.) You can write down explicit formulas for the $p$'s in terms of the $x$'s, $y$'s and $z$'s using Cramer's rule. By Tarski's theorem, there is an algorithm that decides whether any collection of polynomial inequalities has a real solution. I was not able to find any literature about the complexity of this case.

  • Switching to continuous embeddings, the main result of "Embeddability in the 3-sphere is decidable" is that this is decidable and the main result of "Embeddability in $\mathbb{R}^3$ is NP-hard" is that it is NP-hard. I couldn't find any references saying whether or not the problem is in NP. The first paper also shows that continuous and PL-embeddability are equivalent. Disclaimer: I haven't read either paper.

$\endgroup$
4
  • $\begingroup$ When you say “I don’t know an efficient algorithm in general,” does that imply that you know some (albeit inefficient) algorithm? Personally, I have no idea how I would even begin to determine this. What are the steps you could take to show that the shape (hypergraph) is non-embeddable in a given space? $\endgroup$ Dec 9, 2022 at 20:15
  • 1
    $\begingroup$ I'm about to edit in more information about algorithms ... $\endgroup$ Dec 9, 2022 at 20:17
  • $\begingroup$ Thank you so much for the detailed answer! I really should learn Linear Algebra and projective geometry prior to asking any more questions, and I’m gonna go ahead and read everything you linked to. And I’m not complaining about the usage of Linear Algebra and projective geometry, since a question of this nature necessarily delves into deeper topics like these. $\endgroup$ Dec 10, 2022 at 6:01
  • 1
    $\begingroup$ I edited the decscription of the minimal counter-example above to make it more user friendly. Once you get to general algorithms, you are not going to get a simple answer. $\endgroup$ Dec 11, 2022 at 13:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .