Imagine you have a finite number of "sites" $S$ in the positive quadrant
of the integer lattice $\mathbb{Z}^2$,
and from each site $s \in S$, one connects $s$ to every lattice point to which it
has a clear line of sight, in the sense used
in my earlier question: No other lattice point lies along that line-of-sight.
This creates a (highly) nonplanar graph;
here $S=\{(0,0),(5,2),(3,7),(11,6)\}$:
Now, for every pair of edges that properly cross in this graph, delete the longer edge,
retaining the shorter edge.
In the case of ties, give preference to the earlier site, in an initial sorting of
the sites.
The result is a planar graph, because all edge crossings have been removed:
Q1. Is this graph $4$-colorable?
Some nodes of this graph (at least those on the convex hull)
have a (countably) infinite degree. More generally,
Q2. Is every infinite planar graph $4$-colorable?
Which types of "infinite planar graphs" are $4$-colorable?
The context here is that I am considering a type of "lattice visibility Voronoi diagram."
One can ask many specific questions of this structure, but I'll confine myself
to the $4$-coloring question, which may have broader interest.
Best Answer
The answer to both questions is "yes", by the De Bruijn–Erdős theorem.