# Axis-Aligned Square Contact Representations

Andrew Nathenson Research on this paper was partially supported by the NSF
award DMS-1800734. California State University Northridge
<EMAIL_ADDRESS>
###### Abstract

We introduce a new class $\mathcal{G}$ of bipartite plane graphs and prove
that each graph in $\mathcal{G}$ admits a proper square contact
representation. A contact between two squares is _proper_ if they intersect in
a line segment of positive length. The class $\mathcal{G}$ is the family of
quadrangulations obtained from the 4-cycle $C_{4}$ by successively inserting a
single vertex or a 4-cycle of vertices into a face.

For every graph $G\in\mathcal{G}$, we construct a proper square contact
representation. The key parameter of the recursive construction is the aspect
ratio of the rectangle bounded by the four outer squares. We show that this
aspect ratio may continuously vary in an interval $I_{G}$. The interval
$I_{G}$ cannot be replaced by a fixed aspect ratio, however, as we show, the
feasible interval $I_{G}$ may be an arbitrarily small neighborhood of any
positive real.

##  1 Introduction

Geometric representations of graphs have many applications and yield
intriguing problems [9]. Koebe’s celebrated _circle packing theorem_ [8], for
example, states that every planar graph is a contact graph of interior-
disjoint disks in the plane. Schramm [10] proved that this theorem holds even
if we replace the disks with homothets of an arbitrary smooth strictly convex
body in the plane. The result extends to non-smooth convex bodies in a weaker
form (where a homothet may degenerate to a point, and three or more homothets
may have a common point of intersection), and every planar graph is only a
_subgraph_ of such a contact graph.

In this paper, we consider _strong_ contact representations with interior-
disjoint convex bodies where no three convex bodies have a point in common. It
is an open problem to classify graphs that admit a strong contact
representation with homothets of a triangle or a square [1, 2]. It is known
that every partial 3-tree [1] and every 4-connected planar graph admits a
strong contact representation with homothetic triangles, see [5, 6]; but there
are 3-connected planar graphs which do not admit such a representation. We
note here that every planar graph admits a strong contact representation with
(non-homothetic) triangles [3]; see also [6].

Strong contact representations with homothetic squares have been considered
only recently. Da Lozzo et al. [2] proved that every $K_{3,1,1,}$-free partial
2-tree admits a proper contact representation with homothetic squares, where a
contact between two squares is _proper_ if they intersect in a line segment of
positive length (in particular, proper contacts yield a strong contact
representation). Eppstein [4] indicated that another family of graphs, defined
recursively, can also be represented as a proper contact graph of squares. We
remark that Klawitter et al. [7] proved that every triangle-free planar graph
is the proper contact graph of (non-homothetic) axis-aligned rectangles.

(a)

(b)

Figure 1: The two operations used to obtain a graph in $\mathcal{G}$ and their
square contact representations.

#### Contribution.

Let $\mathcal{G}$ be a family of plane bipartite graphs defined recursively as
follows. (i) $\mathcal{G}$ contains the 4-cycle $C_{4}$. (ii) If
$G\in\mathcal{G}$ and $f=(v_{1},v_{2},v_{3},v_{4})$ is a bounded 4-face of
$G$, then $\mathcal{G}$ also contains the graphs $G_{a}$ and $G_{b}$ obtained
by the following two operations: (a) insert a vertex $u$ into $f$ and connect
it to $v_{1}$ and $v_{3}$; (b) insert four vertices $u_{1},\ldots,u_{4}$ into
$f$, add the cycle $(u_{1},u_{2},u_{3},u_{4})$ and the edges $u_{i}v_{i}$ for
$i=1,\ldots,4$; see Fig. 1.

Every maximal 2-degenerate bipartite plane graph can be constructed by
operation (a); and the 1-skeleton of every polycube whose dual graph is a tree
[4] can be constructed by operation (b). However, the two operations jointly
produce a larger class $\mathcal{G}$, which belongs to the class of
3-degenerate bipartite plane graphs. In a square contact representation (SCR)
of a graph in $\mathcal{G}$, every vertex $v_{i}$ corresponds to an axis-
aligned square $s(v_{i})$, and every bounded face to an axis-aligned rectangle
$g(f_{i})$, which is also called the _gap_ corresponding to $f_{i}$. We
present our main result:

######  Theorem 1.1.

Every graph in $\mathcal{G}$ admits a proper square contact representation.

We prove Theorem 1.1 by induction in Section 3. For the induction hypothesis
we establish a stronger version of the theorem in which one specifies
intervals for the aspect ratios (defined as height/width) of every gap in the
representation, then recursively creates the SCR around those gaps.

######  Theorem 1.2.

Let $G\in\mathcal{G}$ be a graph with $n$ vertices and $n-3$ bounded faces
$f_{1},\ldots,f_{n-3}$. For all $\alpha_{1},\ldots,\alpha_{n-3}>0$ and for all
$\varepsilon>0$, the graph $G$ admits a proper square contact representation
such that the aspect ratio of the gap corresponding to $f_{i}$ is
$\alpha_{i}^{\prime}$, with $|\alpha_{i}-\alpha_{i}^{\prime}|<\varepsilon$,
for all $i=1,\ldots,n-3$.

Figure 2: If all the gaps have aspect ratio 1, then scaling any of the squares
to changing the point contacts into proper contacts would change the aspect
ratios of the outer gaps.

Figure 2 shows an example where the aspect ratios of the gaps cannot be
specified exactly in a proper contact representation.

However, it turns out that $\mathcal{G}$ includes graphs that must be bounded
by a rectangle whose aspect ratio is arbitrarily close to any given value, if
they are inserted into a face of another graph in $\mathcal{G}$.

######  Theorem 1.3.

For every $r,\delta>0$, there exists a bipartite plane graph $G\in\mathcal{G}$
with a 4-cycle as its outer face such that in every SCR of $G$, the aspect
ratio of the central gap between the four squares corresponding to that
4-cycle is confined to the interval $(r-\delta,r+\delta)$.

#### Relation to rectangle tilings.

Theorem 1.2 implies a tiling of a bounding box, where the tiles are squares
(of aspect ratio 1) and rectangular gaps whose aspect ratios are prescribed up
to an $\varepsilon$ error term. Note that the contact graph of this tiling,
including squares and gaps, and four additional vertices for the four sides of
the outer frame, is a triangulation. Schramm [11] (see also [9, Chap. 6])
showed that for every inner triangulation $G$ of a 4-cycle without separating
triangles there exists a rectangle contact representation of $G$ in which the
rectangles have prescribed aspect ratios. However, some of the contacts
between rectangles might be point contacts, and the interior of some of the
separating 4-cycles may degenerate to a point. In the recursive construction
of $\mathcal{G}$, step (ii) creates five separating 4-cycles in the
triangulation of the tiling, one for each gap (see Fig. 3). In particular, if
all five gaps degenerate to a point, then Schramm’s result becomes trivial,
but would not imply Theorem 1.2. The class of graphs defined in this paper is
perhaps the first interesting case for which Schramm’s approach is infeasible,
as it cannot guarantee that the rectangles on the interior of the separating
4-cycles do not degenerate.

Figure 3: Left: a rectangular tiling with 9 tiles. Right: the corresponding
triangulation, where the outer 4-cycle corresponds to the four edges of the
outer frame.

#### Outlook.

An obvious open problem is whether every triangle-free plane graph admits a
proper square contact representation. Motivated by Schramm’s results, one can
also ask whether Theorem 1.1 generalizes to the setting where each vertex of
the graph is associated with an axis-aligned rectangle of given aspect ratio.

#### Terminology.

Let $G=(V,E)$ be an edge-maximal plane bipartite graph. In a square contact
representation, every vertex $v_{i}$ corresponds to an axis-aligned square
$s(v_{i})$, and every bounded face to an axis-aligned rectangle $g(f_{i})$,
which is also called the _gap_ corresponding to $f_{i}$. The aspect ratio of
an axis-aligned rectangle $r$ is $\mathrm{height}(r)/\mathrm{width}(r)$. The
side length of a square $s$ is denoted by $\text{len}(s)$. Scaling up a square
from a corner by (or to) $x$ means to increase the width and height of the
square by $x$ (or to $x$) in such a way that the position of the specified
corner remains fixed.

##  2 Maintaining a Square Contact Representation

In this section, we show how to maintain a square contact representation of a
graph in $\mathcal{G}$ under operations (a) and (b). Specifically, we show
that one can insert one or four new squares corresponding to these operations
in a rectangular gap of suitable size. The following Lemmas are used in the
proof of Theorem 1.2 to recursively construct a SCR for any given graph in
$\mathcal{G}$.

######  Lemma 2.1.

For every $\alpha,\beta>0$, there exists an axis-aligned rectangle that can be
subdivided by two horizontal (resp., vertical) lines into three rectangles of
aspect ratios $\alpha$, 1, and $\beta$, respectively.

######  Proof 2.2.

Let $R$ be a rectangle of aspect ratio $\alpha+\beta+1$, with width $x$ and
height $(\alpha+\beta+1)x$. Two horizontal lines at distance $\alpha x$ and
$\beta x$ from the top and bottom side of $R$, resp., subdivide $R$ into
rectangles of aspect ratios $\alpha$, $1$, and $\beta$, as required; see Fig.
4.

Figure 4: Constructing an outer rectangle given two inner rectangle aspect
ratios.

To establish Theorem 1.1, we need a stronger version of Lemma 2.1 that allows
the aspect ratios to vary within a small threshold.

######  Lemma 2.3.

For every $\alpha,\beta,\varepsilon>0$, there exists a $\delta>0$ such that
any rectangle of aspect ratio $\gamma$ with $|\gamma-(\alpha+\beta+1)|<\delta$
can be subdivided by two horizontal lines into rectangles of aspect ratios
$\alpha^{\prime}$, 1, and $\beta^{\prime}$ such that
$|\alpha^{\prime}-\alpha|<\varepsilon$ and
$|\beta^{\prime}-\beta|<\varepsilon$.

######  Proof 2.4.

Let $\delta=\min\\{\alpha,\beta,1,\varepsilon\\}$. Let $R$ be a rectangle of
aspect ratio $\gamma$, where $|\gamma-(\alpha+\beta+1)|<\delta$, with width
$x$ and height $\gamma x$. Two horizontal lines at distance $\alpha x$ and
$(1+\alpha)x$ from the top side of $R$ subdivide $R$ into rectangles of aspect
ratios $\alpha$, $1$, and $\beta^{\prime}=\gamma-\alpha-1$. Note that
$\beta^{\prime}>0$ and
$|\beta^{\prime}-\beta|=|\gamma-(\alpha+\beta+1)|<\delta\leq\varepsilon$.

######  Lemma 2.5.

For every $\alpha_{1},\ldots,\alpha_{5}>0$, there exists an axis-aligned
rectangle $R$ that can be subdivided into four squares and five rectangular
gaps of aspect ratios $\alpha_{1},\ldots,\alpha_{5}$ such that (refer to Figs.
1(b) and 6)

  * •

the four squares are each in contact with a side of $R$, and their contact
graph is a 4-cycle (but the contacts along the 4-cycle are not necessarily
proper);

  * •

the first four gaps are each incident to the top-left, bottom-left, bottom-
right, and top-right corner of $R$, respectively, and the fifth gap lies in
the interior of $R$.

The proof of Lemma 2.5 requires some preparation, and is presented later in
this section. For convenience, we will rename $\alpha_{1},\ldots,\alpha_{5}$
respectively based on the positions of the gaps to which they correspond as
$\alpha_{c}$ (center), $\alpha_{t\ell}$ (top-left), $\alpha_{tr}$ (top-right),
$\alpha_{br}$ (bottom-right), $\alpha_{b\ell}$ (bottom-left). Also, name the
squares incident to the top, bottom, right, and left side of $R$ as $s_{t}$,
$s_{b}$, $s_{r}$, and $s_{\ell}$, respectively.

We will prove Lemma 2.5 by starting with an initial configuration (Fig. 5),
where the aspect ratio of the center gap is already $\alpha_{c}$, and there
are improper contacts between adjacent squares of the cycle. Then we
incrementally modify the configuration, while the center gap remains fixed,
until all remaining gaps have the target aspect ratios $\alpha_{t\ell}$,
$\alpha_{tr}$, $\alpha_{br}$, and $\alpha_{b\ell}$. We denote the current
aspect ratios of these gaps by $g_{t\ell}$, $g_{tr}$, $g_{br}$, and
$g_{b\ell}$ in the same fashion as $\alpha_{t\ell}$
$,\ldots,$$\alpha_{b\ell}$. We next define the initial configuration and four
additional special configurations that play a role in intermediate steps of
the incremental construction.

#### Initial configuration.

To create the initial configuration, we start by drawing the interior gap and
placing $s_{t}$, $\ldots$, $s_{\ell}$ incident to it, with each of their side
lengths equal to the side of the interior gap to which they are incident (see
Fig. 5). Note that the aspect ratios of every outer gap is $\alpha_{c}^{-1}$
in this configuration.

Figure 5: The initial configuration, with squares and gap aspect ratios
labeled.

#### Pinwheel configuration.

A _clockwise_ pinwheel configuration is defined as follows (see Fig. 6(a)):

  * •

the bottom-right corner of $s_{t}$ lies on the left side of $s_{r}$,

  * •

the bottom-left corner of $s_{r}$ lies on the top side of $s_{b}$,

  * •

the top-left corner of $s_{b}$ lies on the right side of $s_{\ell}$,

  * •

the top-right corner of $s_{\ell}$ lies on the bottom side of $s_{t}$.

A _counterclockwise_ pinwheel can be obtained by a reflection.

(a) Clockwise Pinwheel

(b) Vertical Stacked

(c) Downward Arrow

(d) Clockwise Near-Pinwheel with reversed contact between $s_{r}$ and $s_{t}$

Figure 6: Examples of four special configurations.

#### Stacked configuration.

We define a _vertical_ stacked configuration as follows (see Fig. 6(b)):

  * •

the top-right corner of $s_{b}$ lies on the left side of $s_{r}$,

  * •

the top-left corner of $s_{b}$ lies on the right side of $s_{\ell}$,

  * •

the bottom-right corner of $s_{t}$ lies on the left side of $s_{r}$,

  * •

the bottom-left corner of $s_{t}$ lies on the right side of $s_{\ell}$.

A _horizontal_ stacked configuration can be obtained by a $90^{\circ}$
rotation.

#### Arrow configuration.

We define a _downward_ arrow configuration as follows (see Fig. 6(c)):

  * •

the top-right corner of $s_{b}$ lies on the bottom side of $s_{r}$,

  * •

the top-left corner of $s_{b}$ lies on the bottom side of $s_{\ell}$,

  * •

the bottom-right corner of $s_{t}$ lies on the left side of $s_{r}$,

  * •

the bottom-left corner of $s_{t}$ lies on the right side of $s_{\ell}$.

_Upward, leftward_ , and _rightward_ arrow configurations can be obtained by
rotation. We also define the _directional_ square of the arrow configuration
to be the one furthest in the direction after which the configuration is named
(e.g., $s_{b}$ for a downward arrow configuration).

#### Near-pinwheel configuration.

We define a _clockwise_ near-pinwheel configuration as a configuration which
would be a clockwise pinwheel configuration if one of the contacts between
squares was changed from vertical to horizontal, or vice-versa (see Fig.
6(d)). This contact is called the _reversed_ contact of the near-pinwheel
configuration. A _counterclockwise_ near-pinwheel configuration can be
obtained by reflection.

Lemmas 2.6–2.14 below concern transformations of these special configurations,
and are used in the proof of Lemma 2.5.

######  Lemma 2.6.

Assume that the top-left corner of $s_{r}$ is on the right side of $s_{t}$ and
the bottom-left corner of $s_{r}$ is on the right side of $s_{b}$, and let
$\alpha_{tr}$ $>$$g_{tr}$ be given. There exists a $d>0$ such that if we slide
$s_{r}$ upward by $d$ and scale it up by a factor of $d/g_{br}$ from its
bottom-left corner, then no aspect ratio other than $g_{tr}$ changes, and
after the transformation we have $\alpha_{tr}$ = $g_{tr}$, or $\alpha_{tr}$
$>$$g_{tr}$ and $s_{r}$ and $s_{b}$ have a point contact. Similar statements
hold after reflections and rotations of the configuration.

######  Proof 2.7.

Let the bottom-right gap have height $h_{1}$ and width $w$ prior to the
transformation. Assume that we slide $s_{r}$ upward by some amount $d>0$ and
scale it up by a factor of $d/g_{br}$ from its bottom-left corner. After the
transformation, it has height $h_{1}+d$ and width $w+\frac{dw}{h_{1}}$. As

$\frac{h_{1}}{w}=\frac{h_{1}+d}{w+\frac{dw}{h_{1}}},$

the aspect ratio of the bottom-right gap has not changed. Let the height of
top-right gap be $h_{2}$ prior to the transformation, and note that its width
is also $w$. After the transformation, it has height $h-d$ and width
$w+\frac{d}{g_{br}}$. Thus, its height monotonically decreases in $d$, and its
width monotonically increases in $d$, so $g_{tr}$ monotonically decreases in
$d$. We can choose $d=\min(d_{1},d_{2})$, where $d_{1}\geq 0$ is the value
which would reduce the contact between $s_{r}$ and $s_{b}$ to a single point
after the transformation, and $d_{2}\geq 0$ is the value which would achieve
$\alpha_{tr}$ = $g_{tr}$.

######  Lemma 2.8.

A clockwise (counterclockwise) pinwheel configuration can be transformed such
that $g_{br}$ or $g_{t\ell}$ ($g_{tr}$ or $g_{b\ell}$) increases to, or such
that $g_{tr}$ or $g_{b\ell}$ ($g_{br}$ or $g_{t\ell}$) decreases to any amount
$\gamma>0$, while all other aspect ratios remain the same.

######  Proof 2.9.

Assume w.l.o.g. that we are given a _clockwise_ pinwheel configuration, and we
wish to increase the aspect ratio $g_{br}$ to $\gamma>$$g_{br}$. If we scale
up $s_{b}$ from its top-left corner by some amount $d_{1}$, then $g_{b\ell}$
will increase. To account for this change, though, we can scale up $s_{\ell}$
as well so that $g_{b\ell}$ remains constant. Let $h$ be the height of the
central gap. Then,

$g_{bl}=\frac{\text{len}(s_{b})-\text{len}(s_{\ell})+h}{\text{len}(s_{\ell})}.$

After increasing the length of $s_{b}$ by $d_{1}$, we must then increase the
length of $s_{\ell}$ by some amount $d_{2}$ such that

$\frac{\text{len}(s_{b})-\text{len}(s_{\ell})+h}{\text{len}(s_{\ell})}=\frac{(\text{len}(s_{b})+d_{1})-(\text{len}(s_{\ell})+d_{2})+h}{\text{len}(s_{\ell})+d_{2}}$

so that $g_{b\ell}$ does not change. Solving this equation for $d_{2}$ yields

$d_{2}=d_{1}\frac{\text{len}(s_{\ell})}{\text{len}(s_{b})+h}.$

Because $s_{\ell}$ is not in contact with the bottom of $R$,
$\text{len}(s_{\ell})<\text{len}(s_{b})+h$. Thus, $d_{2}<d_{1}$.

Let $w$ be the width of the central gap. Then,

$g_{tl}=\frac{\text{len}(s_{t})}{\text{len}(s_{\ell})-\text{len}(s_{t})+w}.$

After increasing the length of $s_{\ell}$ by $d_{2}$, to maintain $g_{t\ell}$,
we must increase the length of $s_{t}$ by some amount $d_{3}$ such that

$\frac{\text{len}(s_{t})}{\text{len}(s_{\ell})-\text{len}(s_{t})+w}=\frac{\text{len}(s_{t})+d_{3}}{(\text{len}(s_{\ell})+d_{2})-(\text{len}(s_{t})+d_{3})+w}.$

Solving for $d_{3}$ gives

$d_{3}=d_{2}\frac{\text{len}(s_{t})}{\text{len}(s_{\ell})+w}.$

Because $s_{t}$ is not in contact with the left side of $R$,
$\text{len}(s_{t})<\text{len}(s_{\ell})+w$. Thus, $d_{3}<d_{2}$.

After increasing the length of $s_{t}$ by $d_{3}$, we must increase the length
of $s_{r}$ by some amount $d_{4}$ to maintain $g_{tr}$. Similarly to the
argument above, we obtain $d_{4}<d_{3}$, and thus, $d_{4}<d_{1}$.

So, this series of transformations, preserving $g_{tr}$, $g_{t\ell}$,
$g_{b\ell}$, and the central gap, increases the length of $s_{b}$ by $d_{1}$,
which is more than the amount it increases the length of $s_{r}$, $d_{4}$.
Specifically,

$d_{4}=\frac{d_{1}\text{len}(s_{\ell})\text{len}(s_{t})\text{len}(s_{r})}{(\text{len}(s_{b})+h)(\text{len}(s_{\ell})+w)(\text{len}(s_{t})+h)}<d_{1}.$

Before the transformations, the top boundary of $s_{b}$ overlapped the bottom
boundary of $s_{r}$ by some amount $x$. After the transformations, it overlaps
by $x+d_{1}$, because $s_{b}$ has been scaled up from its top-left corner.

The width of the bottom-right gap equals $\text{len}(s_{r})$ minus the length
of the common boundary between $s_{r}$ and $s_{b}$. Because the length of that
common boundary increases by $d_{1}$, but $\text{len}(s_{r})$ increases only
by $d_{4}<d_{1}$, the width decreases. Consequently, the width of the bottom-
right gap decreases and its height increases linearly in $d_{1}$. Overall,
$g_{br}$ monotonically increases in $d_{1}$. We have constructed a series of
transformations that can increase $g_{br}$ to any $\gamma>g_{br}$ with a
suitable $d_{1}$.

######  Lemma 2.10.

A vertical (resp., horizontal) stacked configuration with a point contact
between two of the squares can be transformed such that the aspect ratio of
the outer gap between those squares increases (resp., decreases) to any amount
$\gamma>0$ while all other aspect ratios remain the same.

######  Proof 2.11.

Assume w.l.o.g. that we are given a vertical stacked configuration in which
$s_{r}$ and $s_{b}$ have a point contact, and we wish to increase the aspect
ratio $g_{br}$ to $\gamma>$$g_{br}$.

If there is not a point contact between $s_{\ell}$ and $s_{t}$, then the
following transformation can be applied. Scale up $s_{b}$ from its top-left
corner to increase $g_{br}$. To account for the resulting change in
$g_{b\ell}$, scale up $s_{\ell}$ and translate it downward while maintaining
$g_{t\ell}$, as described in Lemma 2.6. This transformation will either
increase $g_{br}$ to $\gamma$, or it will result in a point contact between
$s_{\ell}$ and $s_{t}$.

If there is a point contact between $s_{\ell}$ and $s_{t}$, then the squares
are arranged in a pinwheel configuration, and by Lemma 2.8 we can increase
$g_{br}$ to $\gamma$ while maintaining all other aspect ratios.

######  Lemma 2.12.

An upward or downward (resp., rightward or leftward) arrow configuration, with
a point contact between the directional square and one of its neighbors, can
be transformed such that the aspect ratio of the outer gap between those
squares increases (resp., decreases) to any amount $\gamma>0$ while all other
aspect ratios remain the same.

######  Proof 2.13.

Assume w.l.o.g. that we are given a downward arrow configuration in which
$s_{r}$ and $s_{b}$ have a point contact, and we wish to increase the aspect
ratio $g_{br}$ to $\gamma$.

If $s_{b}$ and $s_{\ell}$ do not have a point contact, translate $s_{b}$ to
the right while scaling it up in order to maintain $g_{b\ell}$ (as described
in Lemma 2.6) while increasing $g_{br}$ until $g_{br}$ = $\gamma$, or until
there is a point contact between $s_{b}$ and $s_{\ell}$.

If $s_{b}$ and $s_{\ell}$ have a point contact, then scale up $s_{b}$ from its
top-left corner to increase $g_{br}$. To account for the corresponding change
in $g_{b\ell}$, translate $s_{\ell}$ downward while scaling it up to maintain
$g_{t\ell}$ (as described in Lemma 2.6) until $g_{br}$ = $\gamma$, or until
there is a point contact between $s_{\ell}$ and $s_{t}$.

If $s_{\ell}$ and $s_{t}$ have a point contact, then the squares are arranged
in a pinwheel configuration, and by Lemma 2.8 we can increase $g_{br}$ to
$\gamma$ while maintaining all other aspect ratios.

######  Lemma 2.14.

A near-pinwheel configuration can be transformed such that the aspect ratio of
the outer gap in the direction of the near-pinwheel (clockwise or
counterclockwise) from the reversed contact increases to any amount $\gamma>0$
if its left side is the side of a square, or decreases to any amount
$\gamma>0$ if its top side is the side of a square, while all other aspect
ratios remain the same.

######  Proof 2.15.

Assume w.l.o.g. that we are given a clockwise near-pinwheel with a reversed
top-right contact (as in Figure 6(d)), and we wish to increase the aspect
ratio $g_{br}$ to $\gamma$.

Perform the following transformation until $s_{t}$ and $s_{r}$ have a point-
contact or until $g_{br}$ has been increased to $\gamma$. Scale up $s_{b}$
from its top-left corner by some amount. To account for the corresponding
change in $g_{b\ell}$, scale up $s_{\ell}$ from its top-right corner. To
account for the corresponding change in $g_{t\ell}$, scale up $s_{t}$ and
translate it to the left while maintaining $g_{tr}$ as described in Lemma 2.6.

If $g_{br}$ does not reach its target value once $s_{t}$ and $s_{r}$ have a
point contact, then the configuration is a pinwheel, and by Lemma 2.8 we can
increase $g_{br}$ to $\gamma$.

We now have everything needed to prove Lemma 2.5.

######  Proof 2.16 (Proof of Lemma 2.5).

Let $\alpha_{c}$, $\alpha_{t\ell}$, $\alpha_{tr}$, $\alpha_{br}$, and
$\alpha_{b\ell}$ be given. Start with the initial configuration (cf. Fig. 5).
If the target aspect ratios of all four outer gaps are $\alpha_{c}^{-1}$, then
$R$ can be drawn now with aspect ratio $\alpha_{c}$. Otherwise, one or more of
the outer gaps must have their aspect ratios changed, either by increasing or
decreasing them.

Rotate and reflect the initial configuration if necessary such that at least
one gap needs to be made wider (i.e., $\alpha<g$), and the ratio $g/\alpha$ is
maximal for the top-right gap. In order to change $g_{tr}$ to $\alpha_{tr}$,
we can scale up $s_{r}$ from its bottom-left corner until $g_{tr}$ $=$
$\alpha_{tr}$. This scaling will not affect $g_{t\ell}$ or $g_{b\ell}$, but it
will decrease $g_{br}$. After the scaling, the bottom-right gap will either
have the target aspect ratio already, need to be wider yet, or need to be
narrower. From now on, we will not mention the case where a gap has reached
its target aspect ratio already, because it just means that the next step can
be skipped.

If the bottom-right gap needs to be wider yet, then by Lemma 2.6 we can scale
up $s_{r}$ and translate it downward until $g_{br}$ = $\alpha_{br}$ without
changing $g_{tr}$. As $g/\alpha$ is assumed to be maximal for the top-right
gap, if this transformation results in a point contact between $s_{r}$ and
$s_{t}$, it also achieves $g_{br}$ = $\alpha_{br}$ (because otherwise,
$g_{br}$ $>$ $g_{tr}$ = $\alpha_{tr}$).

If the bottom-right gap needs to be narrower, then we can scale up $s_{b}$
from its top-left corner until $g_{br}$ = $\alpha_{br}$. This will increase
$g_{b\ell}$.

Now, we can assume that $g_{tr}$ = $\alpha_{tr}$ and $g_{br}$ = $\alpha_{br}$.
We distinguish between four cases:

  1. 1.

$s_{b}$ has not been scaled, and either $\alpha_{b\ell}$ $\leq\alpha_{c}^{-1}$
or $\alpha_{t\ell}$ $\leq\alpha_{c}^{-1}$.

  2. 2.

$s_{b}$ has been scaled up from its top-left corner, $\alpha_{b\ell}$ $\leq$
$\alpha_{t\ell}$, and $\alpha_{b\ell}$ $\leq\alpha_{c}^{-1}$.

  3. 3.

$s_{b}$ has been scaled up from its top-left corner, $\alpha_{t\ell}$ $\leq$
$\alpha_{b\ell}$, and $\alpha_{t\ell}$ $\leq\alpha_{c}^{-1}$.

  4. 4.

$\alpha_{t\ell}$ $>\alpha_{c}^{-1}$ and $\alpha_{b\ell}$ $>\alpha_{c}^{-1}$.

Case 1: $s_{b}$ has not been scaled, and either $\alpha_{b\ell}$
$\leq\alpha_{c}^{-1}$ or $\alpha_{t\ell}$ $\leq\alpha_{c}^{-1}$. Reflect the
configuration, if necessary, such that $\alpha_{b\ell}$ $\leq$
$\alpha_{t\ell}$. Scale up $s_{\ell}$ from its top-right corner until
$g_{b\ell}$ = $\alpha_{b\ell}$ (making the top-left gap wider). Then, if
$g_{t\ell}$ needs to decrease further, by Lemma 2.6 we can scale up and
translate $s_{\ell}$ until $g_{t\ell}$ = $\alpha_{t\ell}$ to achieve all
target aspect ratios (once again, this transformation guarantees $g_{t\ell}$ =
$\alpha_{t\ell}$ even if it results in a point contact, because we assume
$\alpha_{b\ell}$ $\leq$ $\alpha_{t\ell}$). Otherwise, the top-left gap needs
to be narrower. Since the configuration is a horizontal stacked configuration,
and by Lemma 2.10 we can apply a series of transformations to achieve all
target aspect ratios.

Case 2: $s_{b}$ has been scaled up from its top-left corner, $\alpha_{b\ell}$
$\leq$ $\alpha_{t\ell}$, and $\alpha_{b\ell}$ $\leq\alpha_{c}^{-1}$. Scale up
$s_{\ell}$ from its top-right corner until $g_{b\ell}$ = $\alpha_{b\ell}$.
This transformation decreases $g_{t\ell}$. Then, if $g_{t\ell}$ needs to
decrease further, by Lemma 2.6 we can scale up and translate $s_{\ell}$ until
$g_{t\ell}$ = $\alpha_{t\ell}$ to achieve all target aspect ratios (once again
guaranteed because $\alpha_{b\ell}$ $\leq$ $\alpha_{t\ell}$). Otherwise the
top-left gap needs to be narrower. Since the squares are arranged in a
pinwheel configuration, Lemma 2.8 completes the proof.

Case 3: $s_{b}$ has been scaled up from its top-left corner, $\alpha_{t\ell}$
$\leq$ $\alpha_{b\ell}$, and $\alpha_{t\ell}$ $\leq\alpha_{c}^{-1}$. Scale up
$s_{\ell}$ from its bottom-right corner until $g_{t\ell}$ = $\alpha_{t\ell}$.
This transformation decreases $g_{b\ell}$. Then, if $g_{b\ell}$ needs to
decrease further, by Lemma 2.6 we can scale up $s_{\ell}$ and translate it
downward, maintaining all other aspect ratios, until $g_{b\ell}$ =
$\alpha_{b\ell}$ or $s_{\ell}$ and $s_{t}$ have a point contact. If $s_{\ell}$
and $s_{t}$ have a point contact, then the squares are arranged in a pinwheel
configuration, and Lemma 2.8 completes the proof. Otherwise, $g_{b\ell}$ needs
to increase. Since the squares form a downward arrow configuration in this
case, with a point contact between $s_{b}$ and $s_{\ell}$, Lemma 2.12
completes the proof.

Case 4: $\alpha_{t\ell}$ $>\alpha_{c}^{-1}$ and $\alpha_{b\ell}$
$>\alpha_{c}^{-1}$. We distinguish between two subcases.

Case 4.1: If the top-right corner of $s_{b}$ lies on the bottom side of
$s_{r}$, then by Lemma 2.6, we can translate $s_{b}$ to the left while scaling
it up until $g_{b\ell}$ = $\alpha_{b\ell}$ or $s_{b}$ and $s_{r}$ have a
point-contact, while maintaining all other aspect ratios. If $g_{b\ell}$ =
$\alpha_{b\ell}$, then the configuration is a near-pinwheel and Lemma 2.14
completes the proof. Otherwise, if $s_{b}$ and $s_{r}$ have a point-contact,
then the conditions of Case 4.2 below are satisfied and we proceed as follows.

Case 4.2: If the top-right corner of $s_{b}$ lies on the left side of $s_{r}$,
then scale up $s_{t}$ from its bottom-right corner until $g_{t\ell}$ =
$\alpha_{t\ell}$ and scale up $s_{b}$ from its top-right corner until
$g_{b\ell}$ = $\alpha_{b\ell}$. Now, $g_{tr}$ and $g_{br}$ (which were
previously at their target values) both need to decrease. Reflect the
configuration, if necessary, so that the width of the bottom-right gap needs
to be increased by a larger amount than the top-right gap. Scale up $s_{r}$
from its bottom-left corner until $g_{tr}$ = $\alpha_{tr}$. Then, because the
width of the bottom-right gap needed to be increased by a larger amount of the
two, it still needs to be wider. The configuration is a rightward arrow, so by
Lemma 2.12, we can decrease $g_{br}$ arbitrarily while maintaining the other
aspect ratios.

The following lemma, Lemma 2.17, shows that all improper contacts can be
replaced by proper contacts at the expense of allowing the five aspect ratios
to vary within a given threshold. Using exact values of the aspect ratios,
Lemma 2.5 can only guarantee single-point contacts. However, it is easy to
extend Lemma 2.5 to Lemma 2.17 by changing any improper contacts among
adjacent squares in the 4-cycle into proper contacts.

######  Lemma 2.17.

For every $\alpha_{1},\ldots,\alpha_{5}>0$ and $\varepsilon>0$, there exists a
$\lambda>0$ and a $\delta>0$ such that every axis-aligned rectangle $R$ of
aspect ratio $\lambda^{\prime}$, $|\lambda-\lambda^{\prime}|<\delta$, can be
subdivided into four squares and five gaps of aspect ratios
$\alpha_{i}^{\prime}$, with $|\alpha_{i}^{\prime}-\alpha_{i}|<\varepsilon$,
for $i=1,\ldots,5$ such that

  * •

the four squares are each in contact with a side of $R$, and their contact
graph is a 4-cycle, and all contacts are proper;

  * •

the first four gaps are each incident to the top-left, bottom-left, bottom-
right, and top-right corner of $R$, respectively, and the fifth gap lies in
the interior of $R$.

######  Proof 2.18.

Let $\alpha_{c}$, $\alpha_{t\ell}$, $\alpha_{tr}$, $\alpha_{br}$,
$\alpha_{b\ell}$, and $\varepsilon>0$ be given. By Lemma 2.5, there is a
rectangle $R$ with some aspect ratio $\lambda$ that can be subdivided into
five gaps and four squares $s_{b}$, $s_{t}$, $s_{\ell}$, and $s_{r}$ whose
contact graph is a cycle.

Case 1. Assume first that all four contacts in the cycle are proper. Then
Lemma 2.17 holds with the same $\lambda$. In each case, there exists a square
that can be scaled up or down while maintaining proper contacts in the cycle.
When scaling a single square, the aspect ratio of the bounding box $R$ and
some of the gaps change continuously. By continuity, there exists a $\delta>0$
such that if the aspect ratios of the bounding box is $\lambda^{\prime}$ with
$|\lambda^{\prime}-\lambda|<\delta$, then all five gaps are at most
$\varepsilon$ from their target values.

Case 2. Next assume that one or more contacts in the cycle are improper, i.e.,
two squares intersect in a common corner. For each improper contact, we can
successively scale up one of the two squares to establish a proper contact. We
scale up each square by a sufficiently small amount such that the aspect
ratios of the five gaps change by less than $\varepsilon/2$. Let
$\lambda^{\prime}$ be the aspect ratio of the new bounding box. We can show,
similarly to Case 1, that Lemma 2.17 holds with $\lambda=\lambda^{\prime}$ and
some $\delta>0$ by continuity.

##  3 Proof of Theorem 1.2

Finally, we have all the tools needed to prove Theorem 1.2. We restate it for
convenience:

See 1.2

######  Proof 3.1.

We proceed by induction on $n$, the number of vertices of $G$.

Basis step. Assume that $G=C_{4}$ is a 4-cycle with a single bounded face
$f_{1}$. It is clear that for any $\alpha_{1}>0$, $C_{4}$ has a proper square
contact representation as a pinwheel configuration in which the gap
corresponding to $f_{1}$ has aspect ratio $\alpha_{1}$.

Induction step. Let $G\in\mathcal{G}$ be a graph with $n\geq 5$ vertices, and
assume that the claim holds for all graphs in $\mathcal{G}$ with fewer than
$n$ vertices. Then $G$ was constructed from a graph $G_{0}\in\mathcal{G}$ with
operation (a) or (b) that inserts one or four vertices into a 4-face
$f_{0}=(v_{1},\ldots,v_{4})$. We may assume w.l.o.g. that $v_{1}$ and $v_{3}$
correspond to squares that lie on the vertical sides of the gap corresponding
to $f_{0}$ in any square contact representation. We distinguish between two
cases.

Case (a). Assume that $G$ was obtained from $G_{0}$ by inserting a vertex $u$
into $f_{0}$ and connecting it to $v_{1}$ and $v_{3}$. This operation
subdivides $f_{0}$ into $f_{1}$ and $f_{2}$; and all other faces are present
in both $G$ and $G_{0}$. Let $\alpha_{0}=\alpha_{1}+\alpha_{2}+1$. By Lemma
2.3, there exists a $\delta>0$ such that any rectangle of aspect ratio
$\alpha_{0}^{\prime}$ with $|\alpha_{0}^{\prime}-\alpha_{0}|<\delta$ can be
subdivided by two horizontal lines into rectangles of aspect ratios
$\alpha_{1}^{\prime}$, 1, and $\alpha_{2}^{\prime}$ such that
$|\alpha_{1}^{\prime}-\alpha_{1}|<\varepsilon$ and
$|\alpha_{2}^{\prime}-\alpha_{2}|<\varepsilon$. The induction hypothesis with
$\varepsilon_{0}=\min\\{\varepsilon,\delta\\}$ implies that $G_{0}$ admits a
proper square contact representation such that the gap corresponding to
$f_{0}$ has aspect ratio $\alpha_{0}^{\prime}$, where
$|\alpha_{0}^{\prime}-\alpha_{0}|<\varepsilon_{0}\leq\delta$, and all other
gaps are at most $\varepsilon_{0}\leq\varepsilon$ off from their target aspect
ratios. Lemma 2.3 now yields a subdivision of the gap corresponding to $f_{0}$
into a square in proper contact with the squares corresponding to $v_{1}$ and
$v_{3}$, and two gaps of aspect ratios $\alpha_{1}^{\prime}$ and
$\alpha_{2}^{\prime}$ with $|\alpha_{1}^{\prime}-\alpha_{1}|<\varepsilon$ and
$|\alpha_{2}^{\prime}-\alpha_{2}|<\varepsilon$.

Case (b). Assume that $G$ was obtained from $G_{0}$ by inserting a 4-cycle
$(u_{1},u_{2},u_{3},u_{4})$ into $f_{0}$ and adding the edges $u_{i}v_{i}$ for
$i=1,\ldots,4$. This operation subdivides $f_{0}$ into five faces
$f_{1},\ldots,f_{5}$ of $G$; and all other faces are present in both $G$ and
$G_{0}$.

By Lemma 2.17, there exists an $\alpha_{0}>0$ and a $\delta>0$ such that any
rectangle of aspect ratio $\alpha_{0}^{\prime}$ with
$|\alpha_{0}^{\prime}-\alpha_{0}|<\delta$ can be subdivided into four squares
and five gaps corresponding to $f_{1},\ldots,f_{5}$, of aspect ratios
$\alpha_{1}^{\prime},\ldots,\alpha_{5}^{\prime}$, respectively, such that
$|\alpha_{i}^{\prime}-\alpha_{i}|<\varepsilon$ for $i=1,\ldots,5$. The
induction hypothesis with $\varepsilon_{0}=\min\\{\varepsilon,\delta\\}$
implies that $G_{0}$ admits a proper square contact representation such that
the gap corresponding to $f_{0}$ has aspect ratio $\alpha_{0}^{\prime}$, where
$|\alpha_{0}^{\prime}-\alpha_{0}|<\varepsilon_{0}\leq\delta$, and all other
gaps are at most $\varepsilon_{0}\leq\varepsilon$ off from their target aspect
ratios. Lemma 2.17 now yields a subdivision of the gap corresponding to
$f_{0}$ into four squares, each in contact with a unique one of
$v_{1},\ldots,v_{4}$ and cyclically in contact with one another, and five gaps
of aspect ratios $\alpha_{1},\ldots,\alpha_{5}$ with
$|\alpha_{i}^{\prime}-\alpha_{i}|<\varepsilon$ for $i=1,\ldots,5$.

##  4 Proof of Theorem 1.3

######  Lemma 4.1.

For every integer $n>2$, $K_{2,n}\in\mathcal{G}$; and in any SCR of $K_{2,n}$,
if the squares corresponding to the partite set of size two have side lengths
$\ell_{1}$ and $\ell_{2}$, then the distance between these squares is less
than $\frac{\min(\ell_{1},\ell_{2})}{n-2}$.

######  Proof 4.2.

Let $s_{1}$ and $s_{2}$ be the squares of side lengths $\ell_{1}$ and
$\ell_{2}$, respectively, in some SCR of $K_{2,n}.$ W.l.o.g., we may assume
that $\ell_{1}\geq\ell_{2}$ and that $s_{1}$ is below $s_{2}$. There exists a
rectangle between $s_{1}$ and $s_{2}$ whose top side is the side of $s_{2}$
and whose height is the distance between $s_{1}$ and $s_{2}$. It is clear that
at most two of the $n$ squares corresponding to the other partite set can be
anything but fully contained in this rectangle (see Figure 7). Thus, the other
$n-2$ squares must be inside this rectangle, and each must have the same side
length because they contact the top and bottom of this rectangle. Furthermore,
the sum of their side lengths is less than $\ell_{2}$, because the squares
don’t overlap. Thus, each of these squares has height less than
$\frac{\ell_{2}}{n-2}$, and the distance between $s_{1}$ and $s_{2}$ is less
than $\frac{\ell_{2}}{n-2}$.

Figure 7: At most two squares are outside of the rectangle between $s_{1}$ and
$s_{2}$.

See 1.3

######  Proof 4.3.

Let $r,\delta>0$ be given. By applying a $90^{\circ}$ rotation, if necessary,
we may assume that $r\in[1,\infty)$.

To construct $G$, we first construct its SCR. We start with the 4-cycle, and
successively insert squares into a remaining gap (defined below). After $i$
iterations, we obtain a graph $G_{i}$. We also maintain an interval $I_{i}$
such that $r\in I_{i}$ and in _every_ SCR of $G_{i}$, the aspect ratio of the
central gap must be in $I_{i}$. Initially, we set $I_{0}=(0,\infty)$. We show
that $I_{i+1}\subset I_{i}$ and $|I_{i}|<2^{-i}$ for all $i\in\mathbb{N}$.
Consequently, $I_{i}\subset(r-\delta,r+\delta)$ when $2^{-i}<\delta$, and we
can return $G=G_{i}$.

In each iteration, we repeatedly insert a square into a gap in the SCR
contacting either the top and bottom of the gap, or the left and right.
Clearly, the contact graph corresponding to the resulting SCR will be a
2-degenerate plane bipartite graph. Whenever we insert a square into a gap, we
will also assume that it contacts one additional side of the gap; however,
instead of an actual contact, we can only guarantee that in any SCR, they are
sufficiently close to that side (cf. Lemma 4.1): If the square contacts the
left and right, then it must be very close to the bottom; if it contacts the
top and bottom, then it must be very close to the left. Specifically, if $m$
is the total number of squares used in the rest of the construction, and
$\ell$ is the side length of the largest square used in the construction, we
can insert $\lceil\frac{2m\ell}{\delta}+2\rceil$ squares in between each
square and the side it is supposed to be close to. This will ensure that each
square is at most $\frac{\delta}{2m}$ apart from the side it is supposed to be
close to, and thus that the aspect ratio differs from what the aspect ratio
would be if these contacts actually existed by less than $\frac{\delta}{2}$.
We can carry out the rest of the proof under the assumption that these squares
in fact contact that side, and that the interval for the target aspect ratio
is $(r-\frac{\delta}{2},r+\frac{\delta}{2})$.

Because of these assumed additional contacts, there is always only one
remaining gap in the course of the recursive construction. We will call this
the _remaining_ gap.

Let the aspect ratio of the central gap (of the outer 4-cycle) be constrained
to the interval $I_{i}$. When we insert a square into the remaining gap,
either the lower or upper bound on this aspect ratio will become constrained
to some $c\in I_{i}$. Specifically, after inserting a square which contacts
the left and right (and the bottom, as an additional contact) of the remaining
gap, the lower bound increases to $c$ and the upper bound is unchanged. This
follows because the inserted square must be at least the width of the
remaining gap, so the remaining gap’s aspect ratio must be at least 1.
However, it does not impose any constraint on the maximum height of the
remaining gap, since the top of the square does not contact the top of the
gap. Similarly, after inserting a square which contacts the top and bottom
(and left) of the remaining gap, the height of the gap is limited to the
height of the square, so the remaining gap’s aspect ratio must be at most 1,
while the width of the gap is no further constrained. As we will show later,
the central gap’s aspect ratio varies monotonically in the aspect ratio of the
remaining gap. Thus, we know that some $c$ must exist because inserting a
square which contacts the top and bottom and inserting a square which contacts
the left and right will each change a different one of the bounds of the
aspect ratio of the remaining gap, and hence the central gap, to the same
value.

So, one can always insert a sequence of squares contacting either the top and
bottom or the left and right of the remaining gap, and it will either increase
the lower bound or decrease the upper bound of the interval $I_{i}$, while
containing the target aspect ratio $r$. In the remainder of the proof, we
choose a specific sequence of insertions and show that both the upper and
lower bounds converge to $r$.

#### Phases.

Each iteration of the construction will consist of inserting squares into the
remaining gap, $g$, in two _phases_. In each phase, we will either insert some
number of squares which contact the left and right edges of the gap (a
_vertical_ phase) or some number of squares with contact the top and bottom (a
_horizontal_ phase). The number of squares inserted is the _size_ of that
phase. Because the squares in each phase contact the same two sides of the
gap, each phase will either increase the lower bound or decrease the upper
bound of the interval $I_{i}$. W.l.o.g., let the next phase to insert be
horizontal, setting some upper bound on the aspect ratio of $g$. Then, by
Lemma 4.1, we can insert a sufficiently large phase to reduce the distance
between the last square in this horizontal phase and the side of $g$ to an
arbitrarily small value, bringing the lower bound of the aspect ratio of $g$
arbitrarily close to the upper bound. Because the central gap’s aspect ratio
varies monotonically in the aspect ratio of $g$, for any vertical (resp.,
horizontal) phase, there exists a $k$ for which inserting a phase of size
$k+1$ would bring the lower (resp., upper) bound of $I_{i}$ above (resp.,
below) $r$.

We will use the following process to construct a SCR whose central gap’s
aspect ratio is constrained to $(r-\delta,r+\delta)$, assuming $r\geq 1$. Let
the interval which is the bounds of the central gap’s aspect ratio be
$I_{i}=(a_{i},b_{i})$. Starting with the four outer squares, while
$|I_{i}|\geq\frac{\delta}{2}$:

  1. 1.

Insert a vertical phase whose size is the largest possible such that
$a_{i}\leq r$.

  2. 2.

Insert a horizontal phase whose size is the largest possible such that
$b_{i}\geq r$.

Let $n$ be the total number of iterations.

#### Convergence.

It is clear from the construction that $r\in I_{i+1}\subset I_{i}$ for all
$i\in\mathbb{N}$. It remains to show that $|I_{i}|\leq 2^{-i}$. To prove the
convergence, we will construct the same SCR from the inside-out. We start with
an arrangement which is just the remaining gap, a rectangle, and add phases of
squares alternatively contacting the left and bottom of this arrangement, as
shown in Figure 8. After adding phases in this way, the four outer squares can
be added so that this construction ends with the same SCR as we constructed
with the above process.

Figure 8: Starting with the remaining gap, we add a horizontal phase of
squares (labeled $s_{1},\ldots,s_{k}$ in this figure), then a vertical phase
($t_{1},\ldots$), and will continue with alternating phases.

Let the width of the configuration after adding $i$ vertical phases be 1, and
the height $h$ (and thus, the aspect ratio), be in some interval
$J_{i}=(c,d)$. In particular, note that $J_{0}=(0,\infty)$ and $J_{n}=I_{n}$.
We will then add a horizontal phase of size $k$, then a vertical phase of size
$\ell$. Note that each square in the horizontal phase has side length $h$, and
each square in the vertical phase has side length $kh+1$. Thus, the aspect
ratio of the arrangement after inserting these phases is now

$\frac{(kh+1)\ell+h}{kh+1}.$

This expression shows that $|J_{i}|<\infty$ for all $i\geq 1$. By adding an
extra iteration with $k_{0},\ell_{0}=1$ we can also guarantee that $J_{0}<1$.
We can transform this expression as follows:

$\frac{(kh+1)\ell+h}{kh+1}=\frac{(k\ell+1)h+\ell}{kh+1}=\frac{k\ell+1}{k}-\frac{\frac{1}{k}}{kh+1}.$

This shows that the aspect ratio of the central gap varies monotonically in
the aspect ratio of the remaining gap (as noted earlier).

As $\frac{k\ell+1}{k}$ is a positive constant, it does not affect the length
of the interval $J_{i+1}$. Thus, we can say now that

$\displaystyle|J_{i+1}|$
$\displaystyle<\frac{1}{k}\,\left|\frac{1}{kd+1}-\frac{1}{kc+1}\right|$
$\displaystyle<\frac{|c-d|}{(kc+1)(kd+1)}.$

We know that $d$ is at least 1, because $r\geq 1$, and $k$ is at least 1 as
well. Thus, the denominator is at least 2, and since $|J_{i}|=d-c$,

$|J_{i+1}|<\frac{|J_{i}|}{2}.$

Combined with $|J_{0}|<1$, this implies $|I_{n}|=|J_{n}|<2^{-n}$, and so
$|I_{n}|<\delta$ if $2^{-n}<\delta$, or equivalently, $n>\log\delta^{-1}$.

### Acknowledgements

The author would like to thank Stefan Felsner for bringing to his attention
the connection to Schramm’s square tiling result. Additionally, he would like
to thank Csaba Toth for all of his help and support in presenting these
results.

## References

  * [1] Melanie Badent, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Stefan Felsner, Francesco Giordano, Jan Kratochvíl, Pietro Palladino, Maurizio Patrignani, and Francesco Trotta.  Homothetic triangle contact representations of planar graphs.  In Proc. 19th Canadian Conference on Computational Geometry (CCCG), pages 233–236, Ottawa, ON, Canada, 2007. Carleton University.  URL: http://cccg.ca/proceedings/2007/09b4.pdf.
  * [2] Giordano Da Lozzo, William E. Devanny, David Eppstein, and Timothy Johnson.  Square-contact representations of partial 2-trees and triconnected simply-nested graphs.  In Proc. 28th Symposium on Algorithms and Computation (ISAAC), volume 92 of LIPIcs, pages 24:1–24:14. Schloss Dagstuhl, 2017\.  doi:10.4230/LIPIcs.ISAAC.2017.24.
  * [3] Hubert de Fraysseix, Patrice Ossona de Mendez, and Pierre Rosenstiehl.  On triangle contact graphs.  Comb. Probab. Comput., 3:233–246, 1994.  doi:10.1017/S0963548300001139.
  * [4] David Eppstein.  Square contact graphs, 2017.  URL: https://11011110.github.io/blog/2017/10/03/square-contact-graphs.html.
  * [5] Stefan Felsner and Mathew C. Francis.  Contact representations of planar graphs with cubes.  In Proc. 27th Symposium on Computational Geometry (SoCG), pages 315–320. ACM Press, 2011.  doi:10.1145/1998196.1998250.
  * [6] Daniel Gonçalves, Benjamin Lévêque, and Alexandre Pinlou.  Triangle contact representations and duality.  Discret. Comput. Geom., 48(1):239–254, 2012.  doi:10.1007/s00454-012-9400-1.
  * [7] Jonathan Klawitter, Martin Nöllenburg, and Torsten Ueckerdt.  Combinatorial properties of triangle-free rectangle arrangements and the squarability problem.  In Proc. 23rd Symposium on Graph Drawing and Network Visualization (GD), volume 9411 of LNCS, pages 231–244. Springer, 2015\.  doi:10.1007/978-3-319-27261-0_20.
  * [8] Paul Koebe.  Kontaktprobleme der Konformen Abbildung.  Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl., 88:141–164, 1936.
  * [9] László Lovász.  Graphs and Geometry, volume 65 of Colloquium Publications.  AMS, Providence, RI, 2019.
  * [10] Oded Schramm.  Existence and uniqueness of packings with specified combinatorics.  Israel Journal of Mathematics, 73:321–341, 1991.  doi:10.1007/BF02773845.
  * [11] Oded Schramm.  Square tilings with prescribed combinatorics.  Israel Journal of Mathematics, 84:97–118, 1993.  doi:10.1007/BF02761693.