5
$\begingroup$

By an orthogonal embedding of a finite simple graph I mean an embedding in $\mathbb R^3$ such that each edge is parallel to one of the three axis. To avoid trivialities, let's require that (the embeddings of) two edges may not have any points in common, except obviously a shared vertex. It is clear that orthogonal embeddings can only exist for triangle-free graphs, i.e. graphs of girth at least $4$.
Here are examples of such embeddings for the Dodecahedral Graph (take a regular dodecahedron and "flatten" some edges to "fit" it onto one of the inscribed cubes), the Truncated Octahedral Graph and the Nauru Graph $GP(12,5)$. enter image description here For the Nauru Graph, note that the plane drawing (credits to the Wolfram page) is indeed a projection of a lattice structure existing in $\mathbb R^3$. (This would not be the case for the following plane drawing of $K_{3,3}$.) enter image description here

Such an embedding of a triangle-free cubic graph should exist at least if the graph is planar, which should be easy to show by starting with a polyhedron embedded in $\mathbb R^3$ and then "flattening" parts of that polyhedron in appropriate ways (like for the dodecahedron or the truncated octahedron above), though I have no idea how this could be formalized.

As usual in graph theory, the Petersen graph is a counterexample. For if you take a $C_6$ of the Petersen graph, each pair of opposite vertices has a common neighbor. From this it follows easily that in an orthogonal embedding in $\mathbb R^3$, each $C_6$ must lie in a plane, and thus the whole graph (since any $K_{2,1}$ belongs to two $C_6$'s). Now in $\mathbb R^2$ an orthogonal embedding is obviously impossible.
BTW, the same argument applied to $K_{3,3}$ forces the plane embedding drawn above, showing that $K_{3,3}$ has no orthogonal embedding in $\mathbb R^3$.
Now if we take the cube graph and add an edge joining the midpoints of two opposite edges or of two "skew" edges: no way to embed this orthogonally.
All this raises the question:

What are "good" necessary or sufficient conditions to characterize cubic graphs for which an orthogonal embedding in $\mathbb R^3$ does (or does not) exist?

I am thinking for instance of a criterion in terms of forbidden subgraphs, similar to Kuratowski's theorem for planar graphs: Is there a finite set of forbidden subgraphs which guarantees the existence?

Note that the triangle, the $K_{3,3}$ and the Petersen graph are respectively the $(3,g)$-cage graphs for $g=3,4,5$. The unique $(3,6)$-cage is the Heawood graph, which also has no orthogonal embedding, as can be easily seen by considering two disjoint $C_6$'s in it and the edges connecting those.
Circles bigger than $C_6$ have more degrees of freedom for "folding" them orthogonally in $\mathbb R^3$, so I am wondering specifically:

Is there a minimum girth $g_0$ such that all cubic graphs with girth $\ge g_0$ do have an orthogonal embedding in $\mathbb R^3$?

$\endgroup$
  • $\begingroup$ $K_{2,3}$ is also an obstruction, see Observation 5 in this paper of David Wood (other parts of which are also very relevant for this question) $\endgroup$ – Arnaud Mar 8 at 14:25
  • $\begingroup$ @Arnaud Thank you for the reference! It hasn't yet occurred to me to think about rectangular bends. $\endgroup$ – Wolfgang Mar 8 at 15:19
  • $\begingroup$ I thought you would be familiar with the graph drawing literature on this, but if not, let me also throw in the relevant chapter in the handbook of graph drawing which should also be of interest to you. $\endgroup$ – Arnaud Mar 8 at 15:45
  • $\begingroup$ @Arnaud I wasn't aware this is called drawing rather than embedding! I associate drawings with a plane... $\endgroup$ – Wolfgang Mar 8 at 21:55
  • $\begingroup$ One small remark. If you look for a special drawing in which at each vertex, the 3 incident edges use 3 distinct directions (as in your rightmost drawing), then obviously a necessary condition is that your graph is 3-edge-colorable. This is not the case of the Petersen graph, for instance. And there are cubic graphs of arbitrarily large girth that are not 3-edge-colorable, so they don't have this specific drawing either. $\endgroup$ – Louis Esperet Mar 11 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.