6
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ While it's true that planar graphs are equivalent to graphs that can be embedded on a 2-sphere, the planar embedding will always (as you say) look "roughly circular" and have vertices on one side that don't attach to vertices on the other. Nonetheless, you can re-embed it on the sphere in a nicer, more uniform way. So you shouldn't let that appearance dissuade you. $\endgroup$ – Nick Matteo Apr 22 '13 at 2:30
  • $\begingroup$ Incidentally, a general method to transform a planar embedding into a spherical one is to shrink the unbounded face (outside the graph) down into a small area. So if the outer boundary of the graph has, say, 8 edges, you wrap that up into a little octagonal face the same size as all the others. Then you can go back to a different planar embedding by choosing any face you like, and "blowing it up." $\endgroup$ – Nick Matteo Apr 22 '13 at 2:49
  • $\begingroup$ Related to the original problem more than the sub-questions: you might try a structure like a geodesic sphere or its dual. (see en.wikipedia.org/wiki/Geodesic_dome#Chord_factors) $\endgroup$ – Greg Martin Apr 23 '13 at 1:20
5
$\begingroup$

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.

Rhombicosidodecahedron graph

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.

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

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.

Voronoi tiling of sphere

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.

$\endgroup$
  • $\begingroup$ It is very counter-intuitive that it should be so hard to make vertex-transitive graphs on a sphere when all points on a sphere are interchangeable. The randomization idea is an interesting alternative, since vertices are at least equal in having the same chances at being all the various possible shapes. $\endgroup$ – Geo Apr 23 '13 at 20:22
  • $\begingroup$ Indeed. Maybe the difficulty is related to the hairy ball theorem (that you can't put a continuous vector field on the 2-sphere). (I am just speculating baselessly.) About the Voronoi tiling, I thought the way that the unusual tiles naturally fall into mountain-range-like patterns was intriguing. Also, I believe mountains are usually impassable for most units, so that would greatly lessen their impact on gameplay. I still think that highly non-transitive graphs would be more interesting to play on. $\endgroup$ – Nick Matteo Apr 23 '13 at 20:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.