10
$\begingroup$

By embedding I mean that its edges may intersect only at their endpoints. The precise definition can be found here.

We know that the Petersen graph can be drawn in the plane such that every edge is a segment and has unit length, but that's not an embedding; the edges forming a star-shape intersect each other. We also know that every finite graph can be embedded into the 3-dimensional space with edges not necessarily of unit length.

So I'm interested in the question in the title: is it possible to embed the Petersen graph into the 3-dimensional Euclidean space such that every edge is a segment and has unit length. But it occurred to me that the vertex-position of a pentagon with sides of unit length in the 3D space may be very complicated. So is there any way to handle this?

$\endgroup$
3
  • 2
    $\begingroup$ Are you allowing the edges to have an arbitrary shape that's rectifiable with a length of one, or are you requiring them to be straight lines. I think it's fairly easy to show that an embedding must be possible in the first case. First scale down an arbitrary embedding until all its edges are no longer than one unit, then make all the edges with length less than one squiggly enough so that their length increases to exactly one. $\endgroup$
    – lonza leggiera
    Aug 18 at 14:42
  • $\begingroup$ @lonzaleggiera Ah yes, good observation! I've made the clarification that every edge should be straight lines. $\endgroup$
    – Jianing Song
    Aug 18 at 16:07
  • 1
    $\begingroup$ An interesting question. I guess the answer is positive, but it is not so easy to provide the required construction. So I wrote a letter to two more people dealing with 3D straight line graph drawings. $\endgroup$
    – Alex Ravsky
    Aug 18 at 21:30

1 Answer 1

Reset to default
12
+100
$\begingroup$

There are many embeddings; playing around with this problem, I get the sense that for a typical 3-regular graph, the problem is not very constrained. The only difficulty is that if we look for a particularly symmetric embedding, we increase the risk of intersecting edges. Still, here is one solution I consider particularly nice, in which $7$ of the $10$ vertices are vertices of the unit cube:

enter image description here

The $6$ red vertices are placed at $(1,0,0)$, $(1,0,1)$, $(0,0,1)$, $(0,1,1)$, $(0,1,0)$, $(1,1,0)$. They can be any $6$-cycle you like in the Petersen graph. For concreteness, let's say that they are vertices $\{1,2\}$, $\{3,4\}$, $\{1,5\}$, $\{2,3\}$, $\{1,4\}$, $\{3,5\}$ in the usual construction of the Petersen graph (vertices are $2$-subsets of $\{1,2,3,4,5\}$, disjoint subsets are adjacent).

Opposite vertices of the $6$-cycle have one common neighbor; for this $6$-cycle, these are $\{4,5\}$ (for $\{1,2\}$ and $\{2,3\}$), $\{2,5\}$ (for $\{3,4\}$ and $\{1,4\}$), and $\{2,4\}$ (for $\{1,5\}$ and $\{3,5\}$). These are the purple vertices in the embedding; they are placed at $(\frac12, \frac{2-\sqrt2}{4}, \frac{2+\sqrt2}{4})$, $(\frac{2-\sqrt2}{4}, \frac{2+\sqrt2}{4}, \frac12)$, and $(\frac{2+\sqrt2}{4}, \frac12, \frac{2-\sqrt2}{4})$.

The three purple vertices have one final common neighbor: $\{1,3\}$, which is placed at point $(0,0,0)$.

Here is some Mathematica code for generating a (slightly differently styled) picture of this embedding:

Graph3D[PetersenGraph[], VertexCoordinates -> {
    1 -> {1, 0, 0}, 2 -> {1, 1, 1}, 3 -> {1, 0, 1},
    4 -> {1/2, 1/2 - 1/Sqrt[8], 1/2 + 1/Sqrt[8]},
    5 -> {1/2 + 1/Sqrt[8], 1/2, 1/2 - 1/Sqrt[8]},
    6 -> {1, 1, 0},
    7 -> {1/2 - 1/Sqrt[8], 1/2 + 1/Sqrt[8], 1/2},
    8 -> {0, 0, 1}, 9 -> {0, 1, 1}, 10 -> {0, 1, 0}}]

Unfortunately, the default view of this embedding is not a particularly flattering one, but you can rotate it.

$\endgroup$
1
  • $\begingroup$ Thanks for the excellent answer, that's very nice! $\endgroup$
    – Jianing Song
    Aug 19 at 0:10

You must log in to answer this question.

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