Can there exist an uncountable planar graph?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.