16
$\begingroup$

Is this a theorem?

Every $3$-connected planar graph $G$ may be represented as a tiling of a square by squares, one square per node of $G$, with nodes connected in $G$ corresponding to tangent squares.

Squares

I ask because the cited AMS Notices paper1 suggests that this might be a theorem, offering it as an example of "discrete Ricci flow" and a "generalization of circle packing." But no explicit reference is provided.

There are so many unresolved questions concerning square dissections that it would be interesting to see if this square packing result (if indeed it holds in some form) could address some of the unknowns.

1Gu, Xianfeng, Feng Luo, and Shing Tung Yau. "Computational conformal geometry behind modern technologies." Notices of the American Mathematical Society 67, no. 10 (2020): 1509-1525.

PDF download.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Surely these had better be 3-connected planar graphs, at least. $\endgroup$
    – lambda
    Commented Dec 4, 2020 at 14:26
  • $\begingroup$ @lambda: Oops, you are right. Corrected. Thanks. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 4, 2020 at 14:31
  • 1
    $\begingroup$ What is the proposed connection with Ricci flow? Is the idea to somehow flow to this configuration? $\endgroup$
    – Gabe K
    Commented Dec 4, 2020 at 14:48
  • 1
    $\begingroup$ @GabeK: I don't understand that aspect of their paper. Perhaps I have misinterpreted it. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 4, 2020 at 14:50
  • 1
    $\begingroup$ Maybe the requirement of $3$-connectivity comes from the fact that any little square not located at a corner of the big one has at least three tangent little squares. Moreover, had a square $C$ stuck in a corner at most two tangent squares, then at least one of these tangent squares would have the same size as $C$, which, if I understand the problem correctly, is impossible. $\endgroup$
    – Sylvain JULIEN
    Commented Dec 4, 2020 at 17:03

4 Answers 4

Reset to default
12
$\begingroup$

What does "tangent" mean? If two squares touch only at a vertex, are they tangent? According to the diagram provided, tangent seems to mean that two squares should meet along some (nontrivial) segment of their edges (for instance 23 and 19 meet at a vertex, even though they do not have an edge in common).

If meeting only at a vertex is not counted as being tangent, then the edge graph of a tetrahedron is a counterexample to the proposed theorem (it is not possible to tile a square into 4 squares with each square touching all other squares along a segment of an edge).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Good question, and point! The text says, "Figure 12 shows a generalization of circle packing by replacing circles by squares to compute the extremal length of a combinatorial quadrilateral. The left frame shows a 3-connected graph, with four corner nodes. The right frame shows the extremal length, where each node is replaced by a square with the same label and color. Two nodes are connected in the graph if and only if their corresponding squares are tangent." So perhaps the 4 corner nodes are special? $\endgroup$
    – Joseph O'Rourke
    Commented Dec 4, 2020 at 20:29
  • 2
    $\begingroup$ If you consider the block composed of the squares labeled by 19, 29, 16, and 23, it seems that counting a square sharing only a vertex as "half tangent", each of those 4 squares has 2.5 tangent squares, and 2.5 is precisely the arithmetic mean of the degrees of the corresponding vertices in the subgraph they define. $\endgroup$
    – Sylvain JULIEN
    Commented Dec 4, 2020 at 20:29
  • $\begingroup$ If Schramm is indeed the source, then the graph must be a triangulation of a quadrilateral, and a tetrahedron graph is not a triangulation of a quadrilateral. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 5, 2020 at 13:41
  • $\begingroup$ Well, one could consider the graph obtained by adding a vertex to the middle of a square and connecting that to all the other vertices. This graph is a triangulation of a quadrilateral, but it does not correspond to a tiling of a square. $\endgroup$
    – Mohammad Ghomi
    Commented Dec 5, 2020 at 15:35
  • $\begingroup$ This would suggest that the implication "tiling of a square implies triangulation of a quadrilateral" is not an equivalence. $\endgroup$
    – Sylvain JULIEN
    Commented Dec 5, 2020 at 17:41
2
$\begingroup$

I don't know about having one vertex per square, but there is a similar very interesting construction with edges at squares. It does not answer your question but it will still surely interest you.

Specifically, given a rectangle of height $a$ and width $b$ tiled by squares, you can put a vertex on each horizontal line segment and one edge per square connecting its top and bottom sides. Now, label all edges by the side lenght of the corresponding square and orient them from top to bottom. By seeing the labels as both currents and voltages, note that the resulting graph satisfy Kirchoff two laws, except at the top and bottom vertices. This is fixed by adding an edge from the bottom vertex to the top one with current $b$ and voltage $-a$: we then obtain a $3$-connected planar graph satisfying Kirchoff laws everywhere.

Conversely, given a $3$-connected planar graph with a specified edge $e$, if we impose some voltage $V_1$ on $e$ and resistance $1$ on all other edges, we can solve for all the currents and voltages with Kirchoff laws and this will give us the graph of a rectangle dissection into squares. If the equivalent resistance happen to be $1$, this will mean $a=b$, i.e. the big rectangle is a square.

For more details, this idea is described in chapter 11 of Richard Stanley's Algebraic combinatorics.

Improve this answer
$\endgroup$
2
$\begingroup$

I just found this citation, not cited in the AMS Notices paper (but I cannot yet access the Israel J Math paper itself):

Schramm, Oded. "Square tilings with prescribed combinatorics." Israel Journal of Mathematics 84, no. 1-2 (1993): 97-118. DOI.

Abstract. "Let $T$ be a triangulation of a quadrilateral $Q$, and let $V$ be the set of vertices of $T$. Then there is an essentially unique tiling $Z=(Z_v: v ∈ V)$ of a rectangle $R$ by squares such that for every edge of $T$ the corresponding two squares $Z_u, Z_v$ are in contact and such that the vertices corresponding to squares at corners of $R$ are at the corners of $Q$. It is also shown that the sizes of the squares are obtained as a solution of an extremal problem which is a discrete version of the concept of extremal length from conformal function theory. In this discrete version of extremal length, the metrics assign lengths to the vertices, not the edges."

Because I cannot access the paper, it is unclear to me if this is the source. But it seems like it might be.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Just your regular reminder that anyone on the Internet can very easily access any source associated with a DOI. $\endgroup$
    – Kevin Carlson
    Commented Dec 5, 2020 at 13:06
2
$\begingroup$

My question is answered in Lovász's book:

Lovász, László. Graphs and Geometry. Vol. 65. American Mathematical Soc., 2019.

p.82:

Theorem 6.2. Every planar map in which the unbounded country is a quadrilateral, all other countries are triangles, and is not separated by a $3$-cycle or a $4$-cycle, can be represented as a resolved tangency graph of a square tiling of a rectangle.

Concerning corner touching, Lovász says that, in the case where four squares share a vertex,

we can specify arbitrarily one diametrically opposite pair as "infinitesimally overlapping," and connect the centers of these two square[s] but not the other two squares. We call this a resolved tangency graph of the family of squares.

Indeed the source is Schramm 1993.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .