A periodic layout for the Petersen graph

artgraph theoryplanar-graphs

The Petersen graph is a well-known graph with genus $1$, which means it can be drawn without crossings on a torus. Here is one possible embedding of this type. Topologically, we can think of a torus as a square with opposite sides identified. So every time we draw something on a torus, we can tile the plane with that drawing, and get a periodic picture in the plane.

The Petersen graph has $10$ vertices, and there is a simple $\sqrt{10} \times \sqrt{10}$ square that can tile an infinite grid, as shown in the diagram below:

My question. Is there a nice periodic embedding of the Petersen graph that puts its $10$ vertices down at the points labeled $0$ through $9$ in the diagram above, and connects every point by an edge to some instance of its three neighbors?

The meaning of "nice" is complicated; there are a bunch of mathematical considerations that I am prepared to trade off for an aesthetically pleasing result.

We should definitely be able to draw this in such a way that none of the edges cross. That's what it means for the Petersen graph to have genus $1$.
It would be nice for all the edges to be straight line segments. (This is definitely possible for some embeddings; it may no longer be possible when we put the vertices at these specific points in the grid, but it probably is.)
It would also be nice to have some kind of symmetry or hint of symmetry – for example, different vertices of the embedding having similarly drawn edges out of them, or different faces of the embedding being congruent, aside from what is required by the periodicity.

To illustrate the question a bit more, here is a "near miss". It is a straight-line embedding, and has $180^\circ$ symmetry (almost $90^\circ$ symmetry, in fact) about every point labeled $0$ or $5$, but it is not quite an embedding of the Petersen graph. To be the Petersen graph, it would need an edge between $0$ and $5$.

Best Answer

Here is a non-crossing embedding using only straight line segments of length $1$ and $\sqrt{2}$:

(One nice way to see that this embedding is of a Petersen graph is to note the relatively clean $0-4-3-7-6-0$ and $9-2-5-8-1-9$ cycles, then observe that points on one of the cycles connect to alternating points in the opposite cycle, which easily bijects with this standard view of the Petersen graph.)

It is not very nice, but there are good reasons to think that no solutions with a nontrivial symmetry exist.

The problem is that any reflectional symmetry that does not agree with the existing red grid will, when combined with the tiling across the torus, produce several symmetry constraints that must be obeyed simultaneously, which seems likely to be very difficult. (For instance, being reflectionally symmetric about any one vertical line implies doing so across all vertical lines.)

180-degree rotational symmetries can fare better in this respect, but they cannot be centered around a point without forcing that point to have even degree. I don't see immediate obstructions to central symmetry about an edge or a face of one of the small squares, but running a SAT solver on those constraints with all edges of length at most $5$ didn't turn up any solutions (at least, if my code works properly).

Related Solutions

Reaching the grid graph from a planar graph using graph transformations

There are $5$-regular graphs with $O(k^2)$ vertices from which we can reach the $k \times k$ grid graph using only vertex deletion.

The grid graph has $k^2$ vertices and $2k(k-1)$ edges; to make it $5$-regular by adding edges (I know that's not what you want, but bear with me) we would need to add $\frac12 k^2 + 2k$ edges. I will assume $k$ is even so that this is an integer.

If we are okay with getting a planar multigraph at the end, then this is straightforward. In the $(k-2) \times (k-2)$ interior, double the edges of a perfect matching: now all the interior vertices go up from degree $4$ to $5$. Add a loop at every boundary vertex: now the sides go up from degree $3$ to $5$, and the corners from degree $2$ to $4$. Finally, add two edges that go between the corners.

Now, replace every edge $xy$ we added by the following gadget: an icosahedral graph (a planar $5$-regular graph with $12$ vertices) in which an edge $vw$ is deleted and replaced by edges $vx$, $wy$. Replace every loop at a vertex $x$ by a similar gadget, but with edge $vw$ deleted and replaced by edges $vx, wx$.

The result is a $5$-regular planar graph with $12 \left(\frac12k^2 + 2k\right)$ extra vertices on top of the vertices in the grid graph. In other words, it's a $5$-regular planar graph with $7k^2+24k$ vertices from which we can delete $6k^2+24k$ vertices and get a $k \times k$ grid graph.

Can the Petersen graph be embedded into the 3-dimensional Euclidean space such that every edge is a segment and has unit length

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:

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.

Best Answer

Related Solutions

Reaching the grid graph from a planar graph using graph transformations

Can the Petersen graph be embedded into the 3-dimensional Euclidean space such that every edge is a segment and has unit length

Related Question