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.
Best Answer
It depends on what you consider a plane drawing to be, but how about something like:
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.