There are many possible tilings (or tesselations) of the plane:
- periodic ones by a - necessarily - finite number of prototiles (e.g. regular tilings)
- aperiodic ones by a finite number of prototiles (e.g. Penrose tilings)
- aperiodic ones by an infinite number of prototiles (e.g. arbitrary triangulations)
What I am looking for is a general definition of what a tiling is - in terms of (topological) graph theory. That means:
Given a connected planar graph $G$ and an embedding of $G$ into the plane, i.e. a connected plane graph. What are the conditions on $G$ to be a tiling of the plane?
I won't be surprised if this definition turns out to be trivial, but I don't see it in my mind's eye, yet.
Conditions (necessary and/or sufficient) that spring to mind:
$G$ is 2-edge-connected, i.e. every vertex/edge is contained in a cycle.
If a (topological) connected subset of the plane contains no cycle of $G$, then it is finite.
For aesthetical reasons, I'd like to see the extra condition imposed:
- All minimal cycles of $G$ are convex.
Is there - eventually - a traceable reason for this extra condition?