Finite Vertex-Transitive Planar game of Civilization?

Question

If you have played games in the Civilization series, you will have noticed that the Earth is represented in a simplified and profoundly unsatisfying way. It is wrapped around the curve of a cylinder with impenetrable barriers in the north and south. This is appealing in its simplicity, but very much unlike real geography. For example, here is a thread discussing the problem and possible solutions.

Unfortunately, that thread misses the core of the problem. The real world is homeomorphic to a sphere and all places on the globe are pairwise effectively equivalent. If one has that, then any approximation should be good enough, no matter how distorted the globe becomes. In a strategy game, only the graph truly matters.

Therefore, what I think I want are simple finite vertex-transitive planar graphs. It seems to me that any graph that can be embedded in the surface of a 2-sphere can be embedded in a plane, so focusing on planar graphs seems to make my problem easier. Unfortunately, I have some other goals that aren't as easy to define, such as being able to generate a graph for any given number of vertices, and being able to imagine the vertices distributed roughly evenly over the surface of a sphere with edges connecting nearby vertices. Unfortunately I have no precise way to express that second goal, but I imagine it could be captured by some upper bound on the diameter of the graph. At least I know that I prefer small diameter graphs over large diameter graphs.

Here is an excellent article I found: https://eudml.org/doc/29561

It only deals with degrees 4 and 5, but I find it hard to imagine how it could be much easier for other degrees. There is only one way to create finite vertex-transitive planar graphs of arbitrary size in that article, and it is effectively lining up vertices along two parallels and connecting them with triangles spanning the equator. Graphs like that would have diameter proportional to the number of vertices and wouldn't cover a sphere well.

The article also supplies many other graphs, but each one seems to be individual, with no apparent pattern and so unless I am missing something each would need to be treated as a special case when finding a visually appropriate planar embedding. The planar embedding provided in the article are not appropriate because they are roughly circular instead of allowing vertices on the left side to connect to vertices on the right as one expects in most map projections such as those found in an atlas.

So what I would really like is an algorithm with parameter $n$ that produces a planar embedding of some simple vertex-transitive small-diameter graph with $n$ vertices, where $n$ is allowed to be many possible numbers, and where the embedding is suggestive of a map projection in an atlas.

In addition to that, there are some smaller problems that would surely be useful toward the greater goal:

1. What is the smallest possible diameter for vertex-transitive planar graphs with $n$ vertices? Or what is the largest diameter known to be smaller than the smallest possible diameter?
2. Given $n$, how can one construct a vertex-transitive planar graph with $n$ vertices that has approximately the smallest possible diameter?
3. Assuming there is no answer for the second question, how could one construct a list of all finite vertex-transitive planar graphs for the purpose of searching for graphs with desired properties?

Answer 1

First, a warning about a potential issue as you investigate graphs for this purpose. The graphs you are familiar with in Civilization (square and hexagonal tilings) have the property of being self-dual. That means that what you see in the game—where the faces are tiles, and edges are the boundaries, and units cross the edges—and the abstract graph we're considering here, where units stand on vertices and move along edges, look the same. That's not true in general; in fact, pretty much any other example we'll see for this won't be self-dual, so the depiction on screen won't look like the graph of units moves.

Secondly, I tried to explain in comments why planar embeddings always look circular, but nonetheless correspond to nice embeddings that wrap around a sphere. The key is not to look at the graph as a flat map, but imagine wrapping it over a ball; you'd put the center on one pole, then stretch it over the ball until the outer boundary ends up at the far pole. Consider Figure 2(f) in the paper you cite. This is the graph of a rhombicosidodecahedron; here's another image of it.

When you put this on a sphere, the outer boundary cycle (a pentagon) will just bound a normal-sized pentagonal face; just "lift" that pentagon out of the page, dragging the rest of the graph after it, and shrink it down. You end up with, well, a Rhombicosidodecahedron.

If you have any trouble visualizing that, try following the Wikipedia link for more images and projections.

---

Now, to actually answer the question: I'm afraid there's no solution. The list of all finite, vertex-transitive, planar graphs is known, and none are appropriate for your application. Let's see why:

We're interested in connected, simple graphs (simple meaning that there aren't multiple edges between the same vertices, which would be quite confusing for Civ, and no loops back to the same vertex, which would be worse.) Vertex-transitive graphs obviously have the same degree (number of edges) at every vertex (which is to say, the graph is regular.) A planar graph has a vertex of degree at most 5 (a proof of this well-known fact is discussed in a couple of questions here). So either

• all the vertices have degree 0 (our graph is a point),
• all have degree 1 (a single edge),
• all have degree 2 (a cycle),
• all have degree 3: these cases are covered in the paper Finite planar vertex-transitive graphs of the regularity degree three by Zelinka,
• or all have degree 4 or 5 (these are covered in the paper you cite.)

There are only 3 infinite families among these, the cycles (of degree 2), the prisms (of degree 3: just two $n$-cycles, one inside the other, with corresponding vertices attached), and the antiprisms (of degree 4: see Figure 2(b) in the paper you cite.) None of these are good for Civ. There are only finitely many other examples, enumerated in the two papers given, and all are far too small for Civ (the largest number of vertices I noticed was 120: there might be another with more, but nowhere near enough.)

For yet more takes on this, see Theorem 3 of the paper Transitive Planar Graphs (Fleischner, Imrich '79):

Theorem 3. The connected, simple, planar vertex-transitive graphs are the single vertex, the single edge, simple circuits and the nets of the uniform convex polyhedra, namely the nets of regular prisms and antiprisms, the Platonic and the Archimedian bodies.

or, the Wikipedia article Uniform polyhedron, which says there are only 76 finite uniform polyhedra, which is more or less equivalent.

---

Now that I've told you that your quest is fruitless, I'd like to sound a note of encouragement. You can't do it with vertex-transitive graphs. But this probably isn't what you really want anyway! Having all vertices be the same isn't necessary for strategy—indeed, what drives strategy the most is the fact that locations differ. The existence of choke points, or points that command their surroundings, or points that are more difficult to reach, enable deeper strategy and reward planning. Achieving uniformity would be akin to playing Civ on a featureless plain—not very exciting, right?

So perhaps you should reconsider your requirements and try a different class of graphs. One possibility is Voronoi tessellations: essentially, pick a set of points on your sphere. The faces around each point are the regions which are closer to that point that any other. You will generally end up with something like this, which is formed around a set of random points.

As in this example, almost all the tiles are hexagons (green); a few are pentagons (blue) or heptagons (red). To make this more understandable to the player, you could have the pentagonal and heptagonal tiles be a distinct terrain type. The way that these tiles "run" in the example suggest that mountain ranges would be natural.