Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
I don't understand how a single graph can be a tiling of the plane. Are you asking for the graph to be a tile, copies of which can be used to tile the plane? If so, isn't it just a question of the polygon formed by the outermost edges of the graph, what goes on inside being irrelevant? –  Gerry Myerson Oct 29 '12 at 23:49
@Gerry: Thanks for your comment. I am trying to figure out how my question could be misunderstood this way. I'll try to answer your question as soon as possible. –  Hans Stricker Oct 29 '12 at 23:58
So, if you take a tiling with finitely many prototiles, and take a region containing at least one of each prototile, then that region is the kind of plane graph you are looking for --- is that right? –  Gerry Myerson Oct 29 '12 at 23:58
Never underestimate my ability to misunderstand a question! –  Gerry Myerson Oct 29 '12 at 23:59
+1 by me: And never overestimate my ability to ask a question that cannot be misunderstood. –  Hans Stricker Oct 30 '12 at 0:07
show 1 more comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.