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 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?2012-10-29
  • 0
    @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.2012-10-29
  • 0
    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?2012-10-29
  • 1
    Never underestimate my ability to misunderstand a question!2012-10-29
  • 0
    +1 by me: And never overestimate my ability to ask a question that cannot be misunderstood.2012-10-30
  • 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