I'm currently revising a course on graph theory that I took earlier this year.

While thinking about planar graphs, I noticed that a finite planar graph corresponds to a (finite) polygonisation of the Euclidean plane (or whichever surface you're working with). By considering, for example a full triangulation of the plane, you can find an object that I feel perfectly comfortable considering as a countably infinite planar graph.

Can we take this even further? As soon as you start considering uncountably many vertices, you necessarily get accumulation points in the plane (as the plane is separable). Can we find a (formal) way for the property of being planar to make sense in such a context? Perhaps something along the lines of: "an infinite graph is planar if every finite subgraph is planar."

It seems that our graph can have cardinality at most the continuum, as a planar graph defines a natural injection from the set of vertices into the plane (although perhaps this breaks down if we use the above definition?)

For finite graphs, you can always extend a planar graph to a maximal planar graph. Can we use Zorn's lemma to do the same for arbitrary uncountable planar graph?

For example, if we take the real line as an uncountable path in the sense of graph theory, it certainly feels like it should give an example of a continuum-cardinality planar graph.

Our course mainly focused on finite graphs. Still, we considered a couple of uncountable examples every now and again when there was something interesting to say.

I would be grateful for any insight/references/nudges in a fruitful direction that anybody could provide.

  • $\begingroup$ On second thought, the real line makes no sense as a graph! What would the edges be?! $\endgroup$ – Joshua Pepper Mar 14 '14 at 10:53
  • $\begingroup$ maybe you're interested in this: math.stackexchange.com/q/579772/19341 $\endgroup$ – draks ... Mar 14 '14 at 10:59
  • $\begingroup$ Shelah (1984, 1990) investigates universal graphs with uncountably many vertices. from Wiki:Rado graph $\endgroup$ – draks ... Mar 14 '14 at 11:02
  • $\begingroup$ These links are very interesting! Thanks - I will definitely find time to read through them. Still, since a universal graph contains every finite graph as a subgraph, there is going to be a $K_{3,3}$ and a $K_5$ somewhere, and so it's not going to be planar! $\endgroup$ – Joshua Pepper Mar 14 '14 at 11:05
  • 1
    $\begingroup$ It's not even clear to me that Zorn's Lemma can be used to embed a countable planar graph in a maximal planar graph. If you have a chain of planar graphs ordered by inclusion of the edge sets, each of the graphs can still come with its own idiosyncratic embedding into the plane, so is it obvious that the union of the graphs is still planar? $\endgroup$ – Henning Makholm Mar 14 '14 at 13:14

It depends on what you consider a plane drawing to be, but how about something like:

Put a vertex at $(0,0)$ and one at $(1,x)$ for every $x\in\mathbb R$, with a straight edge going between it and $(0,0)$.

Naively this seems to satisfy the requirements of a planar graph drawing: No point lies on two edges (except endpoints), no vertex lies on an edge it is not an endpoint of, every edge is represented by a continuous path between its endpoints.

On the other hand: A problem with this is that if we consider an abstract graph a topological space (with one point per vertex and a copy of the unit interval for each edge, stitched together in the obvious way), then the topology of the above drawing as a subspace of $\mathbb R^2$ is not the same as that of the graph.

Indeed if we define a "plane drawing" of a graph to be a subset of $\mathbb R^2$ which (with the subspace topology) is homeomorphic to the graph, then there can't be any uncountable planar graph, simply because there's no uncountable discrete subset of $\mathbb R^2$ that can be the image of the vertices.

On the other other hand: There are some topological subtleties hidden beneath "stitched together in the obvious way" here. Actually, as soon as there's a node with countable degree the most obvious way of stitching together (resulting in a quotient space) gives something that is not homeomorphic to a straightforward drawing of the graph -- such as a node at $(0,0)$ and one at $(1,n)$ for every $n\in\mathbb N$, with a straight edge to $(0,0)$. This can be fixed, though, by definig the stiching in a slightly more ad-hoc way which gives a different topology on the abstract graph.

  • $\begingroup$ This is a good example, thanks - and excellent comments about the topology of the graph. Clearly, this question will be extremely sensitive to the definition of planar that we choose. $\endgroup$ – Joshua Pepper Mar 14 '14 at 13:38

For another example, consider the graph with vertices $\{(0,x), (1,x) : x \in \mathbb{R} \setminus \mathbb{Q}\}$, and for each $x$ an edge between $(0,x)$ and $(1,x)$ represented by a horizontal line segment. In this case, for vertices $v,w$, there is an arc joining $v,w$ if and only if $v \sim w$.

You could make this connected by joining every vertex $(0,x)$ to $(-1,0)$ by a diagonal line segment.

As Henning says, as a subspace $A$ of $\mathbb{R}^2$ this is not homeomorphic to the graph $G$. However, there is a continuous injection $G \to A$.

For a more trivial example, consider the graph whose vertices are all the points $(x,y)$ where both $x,y$ are irrational, and with no edges. This has the same property.

  • $\begingroup$ Thanks. These examples suggest that I might want to consider requiring my planar graph to be connected. (Btw, do you mean a horizontal line segment in your first paragraph?) $\endgroup$ – Joshua Pepper Mar 14 '14 at 14:12
  • $\begingroup$ @JoshuaPepper: Yes, I did. Fixed, thanks. $\endgroup$ – Nate Eldredge Mar 14 '14 at 14:52
  • 1
    $\begingroup$ @JoshuaPepper: I also added a connected example. $\endgroup$ – Nate Eldredge Mar 14 '14 at 14:55
  • $\begingroup$ Note that every connected example must contain vertices of uncountable degree (this is independent of planarity). So you can choose between a graph that looks locally nice (finite vertex degrees) or a graph that is globally connected. $\endgroup$ – Henning Makholm Mar 14 '14 at 17:10

The following does not answer your question, but may be interesting.

Call a graph $G$ locally planar if every finite subgraph of $G$ is planar.

Let $F$ be an ordered field. The ordered pairs in $F\times F$ form a "plane." In this plane there is a natural definition of line segment.

Let $V$ be a collection of points of $F\times F$, and let $E$ be a collection of line segments joining some pairs of points of $V$ such that no two line segments in $E$ meet except possibly at endpoints. Then the pair $(V,E)$ defines a graph.

Let $G$ be a graph. Suppose that for the ordered field $F$, and some pair $(V,E)$ of the kind described above, the graph $G$ is isomorphic to the graph $(V,E)$. Then the graph $G$ will be called $F$-planar.

Then the following result holds. Let $\kappa$ be any infinite cardinal. Then there is an ordered field $F_{\kappa}$ such that any locally planar graph of cardinality $\kappa$ is $F_{\kappa}$-planar.

The proof is a straightforward Compactness argument. The field $F_{\kappa}$ can be taken to be an ultrapower of the reals.

  • $\begingroup$ Is it obvious that planar graphs are $\mathbb R$-planar -- that is, that they can be drawn with straight edges without crossings? $\endgroup$ – Henning Makholm Mar 14 '14 at 18:15
  • $\begingroup$ This is a result of several people, including Fary (I have left out an accent). It takes a bit of proving, not hard. The paper is "On straight line representation of finite graphs" Acta Sci. Math. (Szeged) 1948. $\endgroup$ – André Nicolas Mar 14 '14 at 18:19
  • $\begingroup$ Straightening is impossible even for some comparatively nice infinite planar 'graphs'. Dendroids are known to not be straightenable, generally. Though dendrites are straightenable, but that is a tiny piece of the very general objects you all are talking about. $\endgroup$ – John Samples Aug 1 '18 at 3:25

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.