4
$\begingroup$

There are many possible tilings (or tesselations) of the plane:

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?

  • 0
    I understood the question in terms of the graph edges denoting the boundaries between tiles. If so, your graphs would be infinite in many cases, and would always have to be planar. What I don't understad is you asking for a reason for an extra condition, while you described just that reason as “aesthetical” two lines above that. What *other* kind of reason do you expect?2012-10-30

0 Answers 0