Rectangle and Square Representations of Planar Graphs

Abstract

In the first part of this survey, we consider planar graphs that can be represented by a dissections of a rectangle into rectangles. In rectangular drawings, the corners of the rectangles represent the vertices. The graph obtained by taking the rectangles as vertices and contacts as edges is the rectangular dual. In visibility graphs and segment contact graphs, the vertices correspond to horizontal or to horizontal and vertical segments of the dissection. Special orientations of graphs turn out to be helpful when dealing with characterization and representation questions. Therefore, we look at orientations with prescribed degrees, bipolar orientations, separating decompositions, and transversal structures.

In the second part, we ask for representations by a dissections of a rectangle into squares. We review results by Brooks et al. [The dissection of rectangles into squares. Duke Math J 7:312–340 (1940)], Kenyon [Tilings and discrete Dirichlet problems. Isr J Math 105:61–84 (1998)], and Schramm [Square tilings with prescribed combinatorics. Isr J Math 84:97–118 (1993)] and discuss a technique of computing squarings via solutions of systems of linear equations.

Mathematics Subject Classification (2010): 05C10, 05C62, 52C15.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Questions around representations of graphs by geometric objects are intensively studied. Motivation comes from practical applications and the fascinating exchange between geometry and graph theory and other mathematical areas.

One of the nicest results about representations of graphs by geometric objects is Koebe’s “coin graph theorem” [6, 35, 48]. It asserts that every planar graph can be represented by a set of disjoint discs, one for each vertex, such that two discs touch exactly if there is an edge between the corresponding vertices. Such a representation is called a circle contact representation. Figure 1 shows an example.

Fig. 1

A circle contact representation of a planar graph

In the 1980s, Thurston observed a connection between circle packings and the Riemann mapping theorem. From there the theory has developed into a discrete analog of complex analysis; Stephenson’s book [51] gives a comprehensive introduction.

In this chapter, we focus on representations of planar graphs based on rectangles. We look at rectangular dissections as shown in Fig. 2 and graphs that can be derived from it.

Fig. 2

A rectangular dissection

Suppose that $\phi : R \rightarrow {G}_{\phi }(R)$ corresponds to a specific mapping that associates a graph ${G}_{\phi }(R)$ with a rectangular dissection R and that G _ϕ(R) belongs to a class ${\mathcal{G}}_{\phi }$ of graphs. Then we can ask whether a given graph G from class ${\mathcal{G}}_{\phi }$ is representable, i.e., whether G is in the image of ϕ. The representability question can be treated as a characterization problem or as an algorithmic problem. If G is representable, we can also ask for a representation, i.e., for a dissection R such that $G = {G}_{\phi }(R)$. In this survey we consider several graphs associated to a dissection and the corresponding representability and representation problems.

In Sect. 2, we look at rectangular drawings and rectangular duals. Taking the corners of a rectangular dissection as vertices and the connecting line segments as edges yields a rectangular drawing. In Sect. 2.1, we review the theory of rectangular drawings, and in Sect. 2.3, we present an algorithm to decide whether a graph admits such a drawing and, if so, we generate it. The algorithm is based on an orientation of the angular graph with prescribed out-degrees. In some variants of the problem, this approach yields the fastest-known algorithm. In Sect. 2.2, we consider rectangular duals; in this model the vertices of the planar graph are represented by rectangles and edges by contacts.

In Sect. 3, we take the horizontal and vertical segments or just the horizontal segments of a rectangular dissection as vertices. Based on horizontal and vertical segments, we define the segment contact graph of a dissection and then proceed to consider more general segment contact graphs. With Theorem 3.2, we prove an unpublished characterization of segment 2-contact graphs due to Thomassen. In Sect. 3.1.1, segment contact graphs of rectangular dissections are shown to be closely related to separating decompositions. In Sect. 3.2, we consider the visibility graph of a dissection. This leads to the study of bipolar orientations. At the end of the section, in Sect. 3.3, we look at the relation between bipolar orientations and separating decompositions.

In the second part of the survey, we focus on square dissections, i.e., rectangular dissections where all rectangles are squares. Section 4 deals with the square analogs of visibility and segment contact graphs. We begin in Sect. 4.1 with the classical connection between squarings and electricity. In Sect. 4.2, we study a system of linear equations obtained from a separating decomposition and show that a solution yields a squaring. Kenyon [30] developed a more general theory relating trapezoidal dissections and Markov chains; it is the subject of Sect. 4.3.

Section 5 is based on Schramm [49]. The result is a characterization of graphs admitting a square dual. Finally, in Sect. 5.1, we relate square duals and transversal structures and propose an alternative method for computing square duals. The method is simple but comes with the drawback that its correctness still depends on a conjecture.

2 Rectangular Drawing and Rectangular Duals

2.1 Rectangular Drawing

Think of R as a union of interiorly disjoint rectangles. The union of the boundaries of the rectangles is the skeleton $\mathsf{skel}(R)$ of the dissection R. Let C(R) be the set of corners of the rectangles of R. The skeleton of R can be viewed as a graph ${G}_{\mathsf{skel}}(R)$. The vertices of ${G}_{\mathsf{skel}}(R)$ are the points in C(R), and the edges of ${G}_{\mathsf{skel}}(R)$ are the connecting line segments. More formally, the edges correspond to the connected components of $\mathsf{skel}(R) \setminus C(R)$. The skeleton graph ${G}_{\mathsf{skel}}(R)$ has four vertices of degree 2 incident to the outer face. All the other vertices are of degree 3 or 4. The edges are drawn as horizontal or vertical line segments.

If a graph G is represented by R, i.e., $G = {G}_{\mathsf{skel}}(R)$, then we call the representation a rectangular drawing of G. A characterization of graphs with $\Delta \leq 3$ that admit a rectangular drawing was obtained by Thomassen [54]. Thomassen’s result is based on an earlier result of Ungar [59], who gave a characterization in the model where the corners of the outer face are regarded to be bends in an edge instead of vertices of degree 2. Ungar’s characterization is dual to Theorem 2.2.

Algorithms for the construction of rectangular drawings have been considered by various authors. One of the key results is the following.

Theorem 2.1.

Let G be a plane graph with four distinguished corner vertices of degree 2 and vertices of degrees at most 3 otherwise. There is an algorithm that decides whether G is a skeleton graph and if so computes a rectangular drawing in linear time.

A survey of algorithms and many references can be found in Chapter 6 of the book of Nishiseki and Rhaman [43]. In Sect. 2.3, we present an approach to rectangular drawings and a proof of Theorem 2.1 that is not covered there. This leads to improvements in the running times of some variants of the problem.

In the graph drawing literature, rectangular drawings have been extended and generalized in various directions.

• Edges are allowed to bend but remain constrained to the orthogonal drawing mode, i.e., are composed of horizontal and vertical segments. A highlight of the theory is the application of min-cost-flow algorithms for bend minimization pioneered by Tamassia [53].

• To overcome the degree restriction, some authors allow that in the drawing vertices are represented by boxes. With boxes and bends, every planar graph can be represented. If bends are forbidden, the problem can be reduced to finding a rectangular drawing of a derived graph [45].

For more on the topic, we refer to the books on graph drawing [10, 43] and the survey about orthogonal graph drawing [15].

2.2 Rectangular Dual

Let F(R) be the set of rectangles of a rectangular dissection R. It is convenient to include the enclosing rectangle in F(R). The dual of R is the graph ${G}_{\mathsf{{_\ast}}}(R)$ with vertex set F(R) and edges joining pairs of rectangles that share a boundary segment; Fig. 3 shows an example. If a graph G allows a representation as dual of a rectangular dissection R, i.e., $G = {G}_{\mathsf{{_\ast}}}(R)$, then G is called a rectangular dual of R. It is tempting to think that the graph ${G}_{\mathsf{{_\ast}}}(R)$ is the dual graph of ${G}_{\mathsf{skel}}(R)$. This is almost true, but there are some issues about the multiplicity of edges incident to the outer face of ${G}_{\mathsf{skel}}(R)$, i.e., to the enclosing rectangle.

Fig. 3

A rectangular dissection R, its dual ${G}_{\mathsf{{_\ast}}}(R)$, and the dual of the framed dissection R ⁺

Indeed, graphs admitting a rectangular dual may have unwanted features; e.g., a vertex represented by a corner rectangle may have degree 3 and there may be a double-edge between an inner vertex w and the outer vertex v _∞ . A clean characterization is obtained if we assume that the degree of v _∞ is 4. In terms of a rectangular dissection, this can be achieved by adding a frame of four rectangles, one for each side; see Fig. 3.

Theorem 2.2.

A planar triangulation with designated outer vertex v _∞ of degree 4 admits a rectangular dual exactly if it has no separating triangle, i.e., if it is 4-connected.

There are many related characterizations, e.g., Kozḿiński and Kinnen [33] or the earlier result of Ungar [59] in the dual setting. Buchsbaum et al. [2] have many pointers to the literature. An elegant approach to proving the theorem is to split the task into two: In the first step, it is shown that the graph can be enriched with some combinatorial structure. In the second step, this structure is used to construct the geometric representation. Such an approach was taken by Bhasker and Sahni [5] and later refined by He [25], Kant and He [31], and Fusy [22]. The latter two of these papers use transversal structures (cf., Sect. 5.1) as the intermediate combinatorial structure. The approach results in the linear-time construction of rectangular duals with integer coordinates bounded by n.

Problems where some region is to be partitioned into subregions subject to restrictions on the shapes of the subregions and some adjacency constraints are denoted as floor-planning problems. They arise in applications in VLSI chip design and cartography. In view of these applications, specific optimization tasks are of interest. We mention two directions:

• Find a floor plan of a general planar graph such that the shapes of the modules representing the vertices are simple (e.g., orthogonal with ≤ 8 corners) and the total area of the floor plan is small. This problem is studied in [37].

• A rectilinear cartogram is a diagram in which geographic regions have been replaced by orthogonal polygons. The neighbor relation on polygons and on their corresponding regions has to be the same; in addition, the areas of the polygons correspond to some numerical data associated with the regions. Eppstein et al. [16] have studied cartograms where all polygons are rectangles and with the flexibility that they can accommodate arbitrary area assignments. Alam et al. [1] show that a planar triangulation with area assignments can be represented by a cartogram using polygons with 8 corners, which is the best possible.

2.3 An Algorithm for Rectangular Drawings

Let G be the input graph. We assume that G is given with a planar embedding and with four distinguished corner vertices of degree 2; all the other degrees are 3 or 4. With G = (V, E), we consider its trimmed angle graph $\check{A}(G)$. The vertex set of this graph consists of the primal vertex set V together with the dual vertex set save the dual of the unbounded face, i.e., ${V }^{{_\ast}}\setminus \{ {f}_{\infty }\}$. Edges of $\check{A}(G)$ correspond to incidences between vertices and bounded faces of G or equivalently to the internal angles of G. To emphasize the bipartition of $\check{A}(G)$, think of vertices from V as white and of vertices corresponding to faces of G as black vertices; see Fig. 4.

Fig. 4

A planar graph G and its trimmed angle graph $\check{A}(G)$

If G has a rectangular drawing, i.e., $G = {G}_{\mathsf{skel}}(R)$ for some rectangular dissection R, then we can classify the angles of G as either being a corner or being flat with respect to R. We note the following:

• Each inner face is represented as a rectangle and thus has exactly four corner angles.

• Each inner vertex of degree 3 has exactly one flat angle.

Orient the edges of $\check{A}(G)$ such that {v, f} is oriented as f → v when v is a corner of the rectangle corresponding to f and as v → f when the angle is flat. Now consider the out-degrees of this orientation and note that

• $\mathsf{out\text{ -}deg}(f) = 4$ for all black vertices f. For a white vertex v, we have $\mathsf{out\text{ -}deg}(v) = 1$ if v is an inner vertex of G with deg(v) = 3 and $\mathsf{out\text{ -}deg}(v) = 0$ if deg(v) = 4 or if v is a vertex of the outer face of G.

An orientation of $\check{A}(G)$ obeying the above rules for the out-degrees is denoted an ${\alpha }_{\mathsf{skel}}$-orientation.

Theorem 2.3.

Let G be a plane graph with four distinguished corner vertices of degree 2 at the outer face and vertices of degrees 3 or 4 otherwise. There is a rectangular drawing of G if and only if $\check{A}(G)$ has an ${\alpha }_{\mathsf{skel}}$ -orientation.

Proof.

From the above we know that if $G = {G}_{\mathsf{skel}}(R)$ for some R, then there is an ${\alpha }_{\mathsf{skel}}$-orientation of $\check{A}(G)$.

For the converse suppose that $\check{A}(G)$ has an ${\alpha }_{\mathsf{skel}}$-orientation. Identify the four corners of a rectangular frame F with the degree-2 vertices of G in clockwise order. From ${\alpha }_{\mathsf{skel}}$, we can read off which vertices of G are corners of a given face f; they are the out-neighbors of f in the orientation. For faces f sharing an edge with the outer face f _∞ of G which is represented by F, we know which corner is top left, top right, bottom right, and bottom left, i.e., the alignment of the rectangles R _f . If we know the alignment of R _f and if faces f and f′ share an edge in G, then we know the alignment of R _f′ . Thus, the alignment can be passed through dual paths to all faces. The claim is that the alignment of R _f is independent of the dual path from f _∞ to f that has been used. This can be established with a homotopy-type argument. The key to the argument is to check that if v is a vertex and f, f′ are faces incident to vn in G, then passing the alignment information from R _f to R _f′ on either of the two paths on the dual cycle around v yields the same result. This amounts to looking at the pictures of Fig. 5 with all possible choices for f and f′. □ 

The alignment of the rectangles is equivalent to a red–blue coloring and orientation of edges of G such that red edges are horizontal with orientation from left to right and blue edges are vertical and oriented downward. The boundary of each face consists of two directed paths in this orientation. The coloring of one of the two paths has a sequence of red edges followed by a sequence of blue edges; this is the upper path. The other path has blue edges followed by red edges and is called the lower path.

Fig. 5

Consistent alignment of rectangles sharing a vertex v; the arrows indicate the underlying ${\alpha }_{\mathsf{skel}}$ orientation of $\check{A}(G)$

We use the red–blue coloring in the following description of how to construct the rectangular dissection R for G. Let p ₀ be the lower path of the outer face f _∞ . Match the blue part of p ₀ to the left side of the frame F and the red part of p ₀ to the bottom side of F. This requires an arbitrary specification of positions for the vertices of degree 3 contained in p ₀. The third edge of each such vertex will have to be extended into the interior of F. From the coloring we know whether it is horizontal or vertical, but we do not yet know its length. Such an initial piece of an edge will be called a stump. Starting from p = p ₀ we add rectangles one by one, always keeping the invariant that the boundary of the set of already placed rectangles is a directed path p from the top left corner to the bottom right corner of F. We now focus on the placement of a new rectangle. Figure 6 shows an ${\alpha }_{\mathsf{skel}}$-orientation and an intermediate stage of the algorithm.

Fig. 6

An ${\alpha }_{\mathsf{skel}}$-orientation and a corresponding rectangular dissection

Along the path p we see some stumps: The first is a red stump on the top side of F, and the last is a blue stump on the right side of F. Therefore, somewhere along p there is a red stump at a vertex v ₁ followed by a blue stump at v ₂. Let p′ be obtained by restricting p to the part between v ₁ and v ₂. We claim that p′ consists of a sequence of blue edges followed by a sequence of red edges. This can be verified as follows: The stump at v ₁ is outgoing and red, and the edge of p′ incident to v ₁ is also outgoing and hence must be blue. Similarly, the edge of p′ incident to v ₂ has to be red. A vertex of p′ where a red edge is ingoing and a blue is outgoing would have a stump, which is impossible since the stumps at v ₁ and v ₂ are consecutive. This completes the proof of the claim. It follows that p′ is the lower path of some rectangle R _f . We place R _f in the unique consistent way inside F and replace p′ in p by the upper path of R _f . We also have to choose positions for the noncorner vertices contained in the upper path of R _f . Unless the top right corner of R _f is the top right corner of F and the dissection is complete, there is at least one new stump at the top right corner of R _f and possibly some more along the upper path. Now the status of the directed path p and its stumps is as before, and so the next rectangle can be placed. □ 

Algorithmically, the construction of $\check{A}(G)$ from a given G and the construction of the rectangle dissection R from a given ${\alpha }_{\mathsf{skel}}$-orientation of $\check{A}(G)$ are both easy and can be done in linear time. The computation of an ${\alpha }_{\mathsf{skel}}$-orientation can be modeled as a flow problem [18] in $\check{A}(G)$ and with methods from [41] be solved in O(n ^1. 5). In [58] it is shown that the computation of an ${\alpha }_{\mathsf{skel}}$-orientation can be reduced to a shortest-path problem. Using the currently fastest algorithm for planar shortest paths [42] yields an overall running time of $O({n\log }^{2}n/\log \log n)$. If the input graph has no vertices of degree 4, we can do even better: We construct a suitably modified dual G _q ^∗ of G having four vertices corresponding to the outer face of G, one for each segment between degree-2 vertices on the outer face. The ${\alpha }_{\mathsf{skel}}$-orientations of $\check{A}(G)$ are in bijection with transversal structures (a.k.a. regular edge labelings) of G _q ^∗ as defined by Fusy [22, 23]. In his thesis [22], Fusy showed that if G _q ^∗ has no separating triangle, then a transversal structure exists and can be computed in O(n) time. This gives an ${\alpha }_{\mathsf{skel}}$-orientation of $\check{A}(G)$ in linear time. The result is summarized in the following.

Theorem 2.4.

Let G be a plane graph with four distinguished corner vertices of degree 2 and vertices of degrees 3 or 4 otherwise. There is an algorithm based on ${\alpha }_{\mathsf{skel}}$ -orientations that decides whether G is a skeleton graph and if so computes a rectangular drawing in O(n) time if $\Delta \leq 3$ and in $O({n\log }^{2}n/\log \log n)$ time if there are vertices of degree 4.

Rahman et al. [44] have a linear-time algorithm for rectangular drawings of graphs with maximum degree $\Delta \leq 3$ even in the case where no plane embedding of the graph is prescribed.

Miura et al. [40] have an O(n ^2. 5 ∕ logn) algorithm to recognize whether a plane graph $G$ with $\Delta = 4$ has a rectangular drawing. Their result is stated in a more general form: They allow an outer face of more complex shape. Since they prescribe which outer vertices are convex (resp.,  concave) corners, the shape of the outer face can be modeled by adapting the out-degrees of ${\alpha }_{\mathsf{skel}}$. Therefore, this generalization is also covered by our approach. This yields a solution with $O({n\log }^{2}n/\log \log n)$ running time.

3 Segment Contact and Visibility Graphs

3.1 Segment Contact Graphs

Think of a rectangular dissection R as a set of segments, some horizontal and some vertical. If R contains no point where four rectangles meet, intersections between segments only occur between horizontal and vertical segments and they involve an endpoint of one of the segments; i.e., they are contacts. Otherwise, we break one of the two segments of each crossing point into two to get a system of interiorly disjoint segments. The segment contact graph ${G}_{\mathsf{seg}}(R)$ of a rectangulation R is the bipartite planar graph whose vertices are the segments of R and whose edges correspond to contacts between segments. From Fig. 7 we see that ${G}_{\mathsf{seg}}(R)$ is indeed planar and that the faces of ${G}_{\mathsf{seg}}(R)$ are in bijection with the rectangles of R and are uniformly of degree 4. Hence, ${G}_{\mathsf{seg}}(R)$ is a maximal bipartite planar graph, i.e., a quadrangulation.

Fig. 7

A rectangular dissection R and two drawings of its segment contact graph ${G}_{\mathsf{seg}}(R)$

If H is some subgraph of ${G}_{\mathsf{seg}}(R)$, then H can also be represented as segment contact graph of some set of interiorly disjoint horizontal and vertical segments in the plane; i.e., H is a segment contact graph. A segment contact representation for H is obtained from R by removing some segments (vertex deletion) and slightly pulling back the ends of some segments to get rid of contacts (edge deletion). The next theorem states that the converse also holds.

Theorem 3.1.

Every planar bipartite graph H admits a contact representation with interiorly disjoint horizontal and vertical segments.

This was shown by Hartman et al. [27] and by de Fraysseix et al. [12]. In the next subsection we sketch a proof of the theorem based on the concept of separating decompositions of quadrangulations.

A contact representation with interiorly disjoint segments such that the intersection of any k + 1 segments is empty is called a k-contact representation. Thomassen characterized the class of graphs admitting a 2-contact representation.

Theorem 3.2.

A planar graph G = (V,E) has a 2-contact representation if and only if $\vert E[W]\vert \leq 2\vert W\vert - 3$ for every subset W of the vertices. As usual, E[W] denotes the set of edges with both ends in W.

Thomassen presented the result at the Graph Drawing Conference 1993 but never published his proof. Below we provide a simple proof based on rigidity theory. The condition stated in the theorem can be efficiently checked; see, e.g.,  Lee and Streinu [39]. Hliněný [26] showed that the recognition of general contact graphs of segments is NP-complete. Actually, he showed that even the recognition of graphs admitting a 3-contact representation is NP-complete.

A related class of graphs is the intersection graphs of segments. A longstanding conjecture dating back to Scheinerman’s Ph.D. thesis was that every planar graph is a segment intersection graph. The conjecture was finally resolved by Chalopin and Gonçalves [8]. Kratochvíl and Kuběna [34] asked whether all complements of planar graphs are segment intersection graphs.

Proof of Theorem 3.2.

The necessity of the condition is easily seen: Let SS be the set of segments of a 2-contact representation of G. For W ⊂ V, let X _W be the set of endpoints of segments in SS corresponding to vertices of W. We have $\vert {X}_{W}\vert = 2\vert W\vert$. There is an injection ϕ from edges in E[W] to points in X _W . Points belonging to the convex hull of X _W , however, cannot be in the image of ϕ. Since the convex hull contains at least three points, we get $\vert E[W]\vert \leq \vert {X}_{W}\vert - 3 = 2\vert W\vert - 3$. □ 

For the converse, we need some prerequisites. A Laman graph is a graph G=(V, E) with $\vert E\vert = 2\vert V \vert - 3$ and | E[W] | ≤ 2 | W | − 3 for all $W \subset V$. Laman graphs are of interest in rigidity theory; see, e.g., [17, 24]. Laman graphs admit a Henneberg construction, i.e., an ordering ${v}_{1},\ldots,{v}_{n}$ of the vertices such that if G _i is the graph induced by the vertices${v}_{1},\ldots,{v}_{i}$, then it holds that G ₃ is a triangle and G _i is obtained from G _{i − 1} by one of the following two operations:

• (H₁ ) Choose vertices x≠y from G _{i − 1} and add v _i with the two edges (v _i , x) and (v _i , y).

• (H ₂ ) Choose an edge (x, y) and a third vertex z from G _{i − 1}, remove (x, y), and add v _i together with the three edges (v _i , x), (v _i , y), and (v _i , z).

In [28] it is shown that planar Laman graphs admit a planar Henneberg construction in the sense that the graph is constructed together with a plane straight-line embedding and vertices stay at their position once they have been inserted. Moreover, the Henneberg construction can start with an outer triangle that remains unchanged throughout the construction.

Now let G be a planar graph fulfilling the condition of the theorem. We may assume that G is Laman since we can easily get rid of edges in a segment contact representation by retracting ends of segments. Consider a planar Henneberg construction ${G}_{3},\ldots,{G}_{n} = G$. Starting from three pairwise touching segments representing G ₃, we add segments one by one. For the induction we need the following invariant:

• After adding the ith segment s _i , we have a 2-contact representation of G _i and there is a correspondence between the cells of the segment representation and the faces of G _i that preserves edges; i.e., if (x, y) is an edge of the face, then one of the corners of the corresponding cell is a contact between s _x and s _y .

From the count of edges, it follows that the endpoints of all the segments except the three outer segments are used in contacts. Therefore, all faces in the segment contact representation are convex. Figure 8 shows how to add segment s _i in the cases where v _i is added by H₁ (resp.,  H₂). It is evident that the invariant for the induction is maintained. □ 

Fig. 8

The addition of segment s _i

3.1.1 Separating Decompositions and Segment Contact Representations

Let Q be a quadrangulation. We call the color classes of the bipartition white and black and name the two black vertices on the outer face s and t. A separating decomposition of Q is an orientation and coloring of the edges of Q with colors red and blue such that

• 1. All edges incident to s are ingoing red and all edges incident to t are ingoing blue.

• 2. Every vertex v≠s, t is incident to a nonempty interval of red edges and a nonempty interval of blue edges. If v is white, then, in clockwise order, the first edge in the interval of a color is outgoing and all the other edges of the interval are incoming. If v is black, the outgoing edge is the last one in its color in clockwise order (see Fig. 9).

Fig. 9

Edge orientations and colors at white and black vertices

Separating decompositions have been studied in [11, 19, 20]. To us they are of interest because of the following lemma.

Lemma 3.3.

A segment contact representation of Q with horizontal and vertical segments induces a separating decomposition of Q.

Proof.

We assume w.l.o.g. that the segment contact representation and the plane embedding of Q are compatible in the sense that for every vertex v, the clockwise order of the edges around v corresponds to the clockwise order of the contacts around segment s _v of v. We also assume that the segments representing s and t are horizontal, s is the bottom and t is the top segment, and their endpoints have no contact with another segment.

An edge of Q is represented by a contact where an endpoint of one segment is touching the interior of another segment. Orient the edge such that the vertex contributing the endpoint is the tail of the oriented edge. This yields a 2-orientation of Q, i.e., an orientation where every vertex except s and t has out-degree 2. Since s is horizontal, all neighbors of s have to be vertical. Tracing this kind of argument through the graph, we conclude that all black vertices are represented by horizontal segments and all white vertices by vertical segments. Color the edge corresponding to the left contact of a horizontal segment blue and the edge of a right contact red. Similarly, the edge induced by the top contact of a vertical segment is blue and the edge of the bottom contact is red. This construction yields a separating decomposition of Q. For an example, see Fig. 10. □ 

Fig. 10

A quadrangulation Q, a segment contact representation of Q, and the induced separating decomposition of Q

In the following, we sketch a construction for the converse. We start with a separating decomposition of Q and construct a segment contact representation. The algorithm behind the construction may not be the fastest and the construction itself not the most flexible tool for further applications. This author has decided to include it because it nicely and unexpectedly combines some combinatorial structures. Details can be found in [19]. To begin, we need some facts.

• Every quadrangulation admits a separating decomposition.

• The red edges of a separating decomposition form a tree rooted at s that spans all vertices except for t. Symmetrically, the blue edges form a tree rooted at t that spans all vertices except for s.

• There exists a simple closed curve that contains all vertices of Q except s and t and avoids all edges of Q such that all red edges are in the interior of the curve and all blue edges are in the exterior. Deleting the piece of this curve that runs in the outer face, we obtain the equatorial line of the separating decomposition.

• By straightening the equatorial line, we obtain a 2-book embedding of Q; see Fig. 11.

Fig. 11

A quadrangulation Q with a separating decomposition S, and the 2-book embedding induced by the equatorial line of S

An alternating layout of a plane tree T is a noncrossing drawing of T such that the vertices are placed on the x-axis and all edges are embedded in the half-plane above the x-axis (or all below). Moreover, for every vertex v, it holds that all its neighbors are on one side; either they are all left of v or all right of v.

It can bee shown that the 2-book embedding of Q obtained from S yields alternating layouts of the two trees of S. The roots of the two trees are the extreme vertices. In addition, black vertices have all their blue neighbors on the left and all their red neighbors on the right, while for white vertices the converse holds.

Figure 12 indicates a bijection between alternating trees and binary trees such that left/right vertices of the alternating tree correspond to left/right leaves of the binary tree.

Fig. 12

A bijection between alternating trees and the binary trees

Modify the 2-book embedding by merging s with its successor into a new vertex s ⁺ and symmetrically t with its predecessor into t ⁺. Then apply the bijection of Fig. 12 to each of the two trees on its side and tilt the picture by 45^∘. The result is a segment contact representation of Q; see Fig. 13.

Fig. 13

The 2-book embedding from Fig. 11 after merging s and t with their respective neighbors and the associated rectangulation

3.2 Visibility Graphs

A family of disjoint horizontal segments in the plane defines a visibility graph. The vertices of the graph are the segments and edges are based on vertical visibility: A segment s′ is visible from segment s if there is a vertical ray r leaving s such that s′ is the first segment in the family reached by r. The visibility graph is undirected since if s′ is visible from s via an up-ray, then there is a down-ray proving visibility of s from s′. However, if we only care about the up-rays, we get a natural orientation of the visibility graph; this orientation is a bipolar orientation. Indeed, bipolar orientations and visibility representations of planar graphs are intimately related. The study of this connection and its use for the construction of visibility representations has been pioneered by Rosenstiehl-Tarjan [47] and Tamassia-Tollis [55].

3.2.1 Bipolar Orientations

Let G be a graph with distinguished adjacent vertices s and t. A bipolar orientation of G is an acyclic orientation of G such that s is the unique source and t is the unique sink; the oriented edge (s, t) is the root of the orientation. A graph G admits a bipolar orientation exactly if G is 2-connected. Actually, the root edge of a 2-connected graph can be chosen arbitrarily. In the literature these facts are frequently treated in the disguise of st-numberings. Sometimes it is convenient to omit the root edge. In a slight abuse of notation, we also speak of a bipolar orientation in this case. This is done, for instance, in the next paragraph and in Fig. 14.

Fig. 14

A dual pair B, B ^∗ of bipolar orientations and the rectangular dissection returned by the algorithm when using B and B ^∗

Bipolar orientations of a plane 2-connected (multi)graph G with designated s and t on the outer face are characterized by two facts:

Fact F.:

Every face f of G has exactly two angles where the orientation of the edges coincide. [The vertices incident to these angles are ${v}_{\mathsf{source}}(f)$ and ${v}_{\mathsf{sink}}(f)$.]

Fact V.:

Every vertex v≠s, t of G has exactly two angles where the orientation of the edges differ. [The faces incident to these angles are ${f}_{\mathsf{sink}}(v)$ and ${f}_{\mathsf{right}}(v)$.]

An orientation of a plane graph G induces an orientation on the dual graph G ^∗: Define the orientation of a dual edge e ^∗ as left to right relative to the orientation of e. That is, when looking in the direction of an oriented edge e, the dual edge e ^∗ is oriented from the left face to the right face of e.

The bipolar dual of a plane bipolar orientation is this dual graph endowed with this dual orientation rooted at $({s}^{{_\ast}},{t}^{{_\ast}})$, where s ^∗ is be the face on the right and t ^∗ is the face on the left of (s, t); i.e, the orientation of $({s}^{{_\ast}},{t}^{{_\ast}})$ is not dual to (s, t). Essentially, facts V and F are dual and we have set up the orientation of the root edge $({s}^{{_\ast}},{t}^{{_\ast}})$ such that the bipolar dual of a plane bipolar orientation is again a bipolar orientation.

A more comprehensive treatment, including proofs of the material in this subsection, can be found in [13], for example.

3.2.2 From a Bipolar Orientation to a Rectangular Dissection

The input of the following algorithm is a 2-connected plane graph G with an oriented root edge (s, t) on the outer face. The output is a rectangular dissection R such that the visibility graph of the horizontal segments of R is G.

3.2.3 Algorithm Rectangular Dissection

• Compute a bipolar orientation B of G with root edge (s, t).

• Compute the bipolar dual B ^∗ with root edge $({s}^{{_\ast}},{t}^{{_\ast}})$ of B.

• For each primal vertex v, let y(v) be the length of the longest directed s → v path in B.

  For each dual vertex f, let x(f) be the length of the longest directed s ^∗ → f path in B ^∗.

• With a primal vertex v≠s, t, associate the horizontal segment with left end at the point $(x({f}_{\mathsf{left}}(v)),y(v))$ and right end at $(x({f}_{\mathsf{right}}(v)),y(v))$. With a dual vertex $f\neq {s}^{{_\ast}},{t}^{{_\ast}}$, associate the vertical segment with lower end $(x(f),y({v}_{\mathsf{source}}(f)))$ and upper end $(x(f),y({v}_{\mathsf{sink}}(f)))$.

  The special vertices s, t, s ^∗, and t ^∗ need special treatment; as endpoints of these four segments we can choose the four points (0, 0), (0, y(t)), (x(t ^∗), y(t)), and (x(t ^∗), 0). If the visibility between s and t is required, the right endpoint of these two segments can be shifted to the right by one unit.

From the algorithm, we obtain

Theorem 3.4.

For a 2-connected planar graph G with n vertices and n ^∗ faces, there is a visibility representation with horizontal segments whose endpoints are on integer points (x,y) with $0 \leq x \leq {n}^{{_\ast}}$ and $0 \leq y \leq n - 1$ . Such a representation can be computed in linear time.

A sketch of the proof of correctness for the algorithm can be found in [10]. A sweep-like proof may, however, be simpler. This could be accomplished by an inductive proof of the statement that the set of segments with y-coordinate ≤ k is a visibility representation of the graph induced by vertices v with y(v) ≤ k.

The bound on the size of the representation accounted for a visibility between s and t.

Quite some research has been put into more compact visibility representations. The basic idea is that a carefully chosen bipolar orientation may have a longest s → t path of length much less than n. Almost optimal bounds are known:

• Zhang and He [60] show that there are planar graphs on n vertices requiring size at least $(\lfloor \frac{2n} {3} \rfloor ) \times (\lfloor \frac{4n} {3} \rfloor - 3)$ for a visibility representation.

• He and Zhang [29] show that every planar graph with n vertices has a visibility representation with height at most $\frac{2n} {3} + 2\lceil \sqrt{n/2}\rceil$. They use properties of Schnyder woods to construct an appropriate bipolar orientation.

• Fan et al. [21] show that every planar graph with n vertices has a visibility representation with width at most $\lfloor \frac{4n} {3} \rfloor - 2$.

• Sadasivam and Zhang [52] show that it is NP-hard to find the bipolar orientation of G which minimizes the length of the longest s → t path.

3.3 Bipolar Orientations and Separating Decompositions

Let again Q be a plane quadrangulation with color classes consisting of black and white vertices. The black graphG _b of Q is the graph on the set V _b of black vertices of G, where u, v ∈ V _b are connected by an edge for every face f of Q incident to u and v; i.e., there is a bijection between faces of Q and edges of G _b . The graph G _b inherits a plane embedding from the plane embedding of Q. Note that in general G _b may have multiple edges.

Let G be a plane graph; the angle graph of G is the graph Q with vertex set consisting of vertices and faces of G, and edges corresponding to incidences between a vertex and a face, and Q inherits a plane embedding from G. If there are no multiple incidences, i.e., if G is 2-connected, then Q is a quadrangulation. The angle graph construction G → Q _G is the inverse of the black graph construction Q → G _b . More precisely, $Q \leftrightarrow {G}_{b}$ is a bijection between plane quadrangulations with a black-white coloring and plane 2-connected multigraphs. An example is given in Fig. 15.

Fig. 15

A quadrangulation Q and its black graph G _b

Changing the role of the color classes we can associate the white graphG _w with Q. By symmetry, $Q \leftrightarrow {G}_{w}$ is again a bijection between plane quadrangulations Q with a black-white coloring and plane 2-connected multigraphs. The induced bijection ${G}_{b} \leftrightarrow {G}_{w}$ is nothing more than the traditional plane duality.

The study of the oriented counterpart of these classical bijections goes at least back to [47] and was continued in [11, 13, 19, 46]. Let B be a plane bipolar orientation on black vertices with the root edge (s, t) on the outer face. Let Q be the angle graph of the underlying undirected graph of B. Facts V and F of bipolar orientations yield two special angles for every v≠s, t of B and for every face of B. At vertices, the special angles are the left and the right angle. At faces, the special angles are the source and the sink angle. Using the correspondence between angles of B and edges of Q, we define a separating decomposition on Q: The edge incident to v in Q that corresponds to the left special angle is outgoing blue, and the edge that corresponds to the right special angle is outgoing red. The edge incident to f in Q that corresponds to the source is red outgoing and the edge corresponding to the sink is blue outgoing. The rules are illustrated in Fig. 16. It is easily verified that they yield a separating decomposition of Q as defined in Sect. 3.1.1.

Fig. 16

From a bipolar orientation to a separating decomposition and back

Starting from a separating decomposition S on Q, we obtain the unique bipolar orientation B on G _b inducing S by using the converse rules: At a vertex v, the two outgoing edges of S split the edges of G _b into two blocks. The block where Q may have blue edges is the block of incoming edges in the bipolar orientation, and the edges of the other block are the outgoing edges in the bipolar orientation. The oriented bijection fits together well with oriented duality; there is only a slight asymmetry concerning the outer vertices and edges.

The correspondence between bipolar orientations and separating decomposition allows us to use the construction from Sect. 3.1.1 for visibility representations and the algorithm from Sect. 3.2.2 for segment contact representations.

4 Square Dissections

In this section, we are mainly interested in square dissections, which are rectangular dissections where all the small rectangles are squares. Again, we are going to look at different graphs associated with such a dissection.

4.1 Squarings and Electricity

The theory of square layouts goes back to a seminal paper, ”The dissection of rectangles into squares,” by Brooks, Smith, Stone and Tutte from 1940 [7]. The story of the collaboration of the four students has been told several times. In [57] Tutte tells his memories. The aim of the four students was to find squarings of a square such that the sizes of all small squares are different. Such a squaring is called perfect; see Fig. 17.

Fig. 17

The essentially unique perfect squaring with the smallest number of squares. It was discovered in 1978 by A.J.W. Duijvestijn

They based the search for perfect squarings on the following idea: Start with a rectangular dissection and try to produce a combinatorially equivalent squaring.

The squaring process could be simplified with some observations: The initial rectangular dissection R can be described by the visibility graph G of the horizontal segments. The rectangles of the dissection are in bijection with the edges of G (this may require multiple edges in G). On G there is the natural upward- pointing bipolar orientation B [the root edge (s, t) can be omitted].

With an arc a of B, associate the width w(a) of the rectangle corresponding to a in R. The function w on the arcs of B respects the flow conservation law in every vertex except s and t; it is an st-flow.

Symmetrically, from the dual graph G ^∗ with the dual bipolar orientation B ^∗ and the height h(a ^∗) of the rectangle associated with a ^∗, an ${s}^{{_\ast}}{t}^{{_\ast}}$-flow is obtained.

If the dissection R were a squaring, then w(a) = h(a ^∗) for every dual pair $a \leftrightarrow {a}^{{_\ast}}$ of arcs.

It can be verified that if we find a function f on G such that with f(e ^∗) = f(e), we have an st-flow on G and an ${s}^{{_\ast}}{t}^{{_\ast}}$-flow on the dual G ^∗, then orienting the edges such that f(a) ≥ 0 yields a bipolar orientation on G. Based on this bipolar orientation, a squaring of G such that f describes the size of the squares can be constructed with a weighted variant of the algorithm from Sect. 3.2.2. An example is shown in Fig. 18.

Fig. 18

A flow with primal and dual flow conservation and the corresponding squaring

Physicists may recognize a flow with primal–dual flow conservation as an electrical flow. Primal and dual flow conservation corresponds to the two Kirchhoff laws. To find an appropriate f, we can thus build G as an electrical network such that each edge has unit resistance and then attach the poles of a battery to s and t and measure the electrical current in each edge. The solution can, of course, also be obtained analytically. In fact, Kirchhoff’s theorem [32] relates the solution to the enumeration of certain spanning trees.

Theorem 4.1.

Let G be a plane graph with special vertices s and t on the outer face. For an edge e ={ u,v} of G, let ${w}_{e} = \vert {n}_{uv} - {n}_{vu}\vert$ , where n _xy is the number of spanning trees T of G such that T contains a path s,..,x,y,..,t. If w _e > 0 for all e, then there is a square layout R with G as visibility graph such that the square associated with e has side length w _e.

Sketch of a proof. We use the duality $T \leftrightarrow {T}^{{_\ast}}$ between spanning trees of G _b and its dual ${G}_{b}^{{_\ast}} = {G}_{w}$. If a tree T contributes to n _uv , then T ^∗ contains the edge $\{{s}^{{_\ast}},{t}^{{_\ast}}\}$. Let f _l and f _r be the faces left and right of (u, v) in G _b , and define $S = T -\{ u,v\} +\{ s,t\}$ and ${S}^{{_\ast}} = {T}^{{_\ast}}-\{ {s}^{{_\ast}},{t}^{{_\ast}}\} +\{ {f}_{l},{f}_{r}\}$. The pair S, S ^∗ is again a dual pair of spanning trees. The mapping $(T,{T}^{{_\ast}}) \leftrightarrow (S,{S}^{{_\ast}})$ yields a bijection between pairs contributing to n _uv and pairs contributing to the dual count ${n}_{{f}_{l}{f}_{r}}^{{_\ast}}$. From the existence of this bijection, it can be concluded that ${w}_{\{u,v\}} = {w}_{\{{f}_{l},{f}_{r}\}}$. □ 

Our proof is taking advantage of the planarity of G. However, for general graphs, the same definition of w _e yields the electrical current in e (up to normalization); see, e.g., [4].

If w _e  = 0 for some edge e, we still get a square layout R. In R the horizontal segments corresponding to the two end vertices of e are merged into a single segment. If all edges with zero flow are isolated, this may be tolerated as consistent with the notion of visibility representation; however, as shown in Fig. 19, more complex parts of a graph can disappear because all their edges have zero flow. A sufficient condition that ensures that edges with zero flow are at least isolated is that the graph is 3-connected (see Proposition 4.5).

Fig. 19

A rectangular dissection R, the bipolar orientation of the visibility graph G obtained from R and the squaring of G with five invisible zero squares in the center

4.2 Squarings and Separating Decompositions

We now come to a different approach to square layouts. Associate a variable with every inner face of a quadrangulation Q. In these variables we set up a system of linear equations such that a nonnegative solution of the system yields a squaring. To define the system of equations, enhance the quadrangulation Q with a separating decomposition S. We aim for a squaring that induces S with its segment contacts.

For a vertex v of Q, let ${\mathcal{F}}_{r}(v)$ be the set of faces incident to v in the angle between the two outgoing edges of v where incoming edges are red, and let ${\mathcal{F}}_{b}(v)$ be the other incident faces of v, i.e., the faces in the angle with blue incoming edges.

Suppose that such a square representation inducing S exists, and let x _a be the sidelength of the square representing a face a of Q. Every inner vertex v implies an equation that has to be fulfilled by the side lengths:

$$\sum\limits_{a\in {\mathcal{F}}_{r}(v)}{x}_{a} = \sum\limits_{a\in {\mathcal{F}}_{b}(v)}{x}_{a}.$$

(1)

A quadrangulation with n vertices has n − 2 faces; hence, we have a system of n − 4 linear equations (inner vertices) in n − 3 variables (inner faces). To forbid the trivial solution of the homogenous system, we let ${\mathcal{F}}_{r}(t)$ be the set of bounded faces incident to t and add the equation ${\sum \limits }_{a\in {\mathcal{F}}_{r}(t)}{x}_{a} = 1$. Rewriting the equations (1) as ${\sum \limits }_{a\in {\mathcal{F}}_{r}(v)}{x}_{a} -{\sum \limits }_{a\in {\mathcal{F}}_{b}(v)}{x}_{a} = 0$ and collecting all of them in a matrix A _S , we find that the vector of side lengths is a solution to the system

$${A}_{S} \cdot x ={ \mathbf{e}}_{\mathbf{1}}.$$

(2)

Given any separating decomposition S of Q, we can consider the corresponding system (2). In the following, we show

• The matrix A _S is nondegenerate; hence, there is a unique solution x to the system.

• If the solution vector x is nonnegative, then there is a squaring with side lengths given by the components of x. If the solution vector x is positive, then the separating decomposition induced by the segment contacts of the squaring is S.

Theorem 4.2.

The matrix A _S is nondegenerate; i.e., det (A _S )≠0.

Proof.

The idea for the proof is to show that $\vert \det ({A}_{S})\vert$ is the number of perfect matchings of an auxiliary graph H _S . Let $\hat{A}_s$ be the matrix obtained from A _S by replacing each − 1 by 1 and note that $\hat{A}_s$ only depends on Q and not on S. It has a 1 for every incidence between an inner face (variable) and an inner vertex or t (equation). Regard $\hat{A} =\hat{ {A}}_{S}$ as the adjacency matrix of a bipartite graph H. From what we said before, the graph H is obtained from the angle graph A(Q) of Q by removing the vertices s, s ^∗, t ^∗ and the vertex corresponding to the outer face of Q together with the incident edges. This implies

• H is planar.

• All inner faces of H are quadrangles.

Consider the Leibniz-expansions of det(A _S ). The nonvanishing summands ${\prod \limits }_{i}{a}_{i\;\sigma (i)}$ are in bijection with the perfect matchings ${M}_{\sigma }$ of H. The contribution of a perfect matching M to $\det ({A}_{S})$ is either + 1 or − 1; it will be denoted ${\mathsf{sign}}_{S}(M) = \mathsf{sign}({\pi }_{M}){\prod \limits }_{ij\in M}{[{A}_{S}]}_{ij}$. □ 

The proof of the theorem relies on the following two claims:

Claim A.:

The graph H has a perfect matching.

Claim B.:

If M and M′ are perfect matchings of H, then ${\mathsf{sign}}_{S}(M) ={ \mathsf{sign}}_{S}(M^{\prime})$.

We first prove Claim A by verifying the Hall condition for H. Let (X, R) be the vertex bipartition of H where X corresponds to the set of inner faces of Q and $R = V (Q) \setminus \{ s,{s}^{{_\ast}},{t}^{{_\ast}}\}$.

The Hall condition for the full angle graph A(Q) is easily verified: Consider a set F of inner faces of Q and let Z be the set of connected components of ${\mathsf{IR}}^{2} \setminus {\bigcup }_{f\in F}\bar{f}$, where $\bar{f}$ is the closure of face f. The set $F \cup Z$ is the set of faces of a planar bipartite graph whose vertices and edges are those incident to elements of F in Q. This graph has at least $\frac{1} {2}(4\vert F\vert + 4\vert Z\vert )$ edges and hence, by Euler’s formula at least $\vert F\vert + \vert Z\vert + 2 \geq \vert F\vert + 3$ vertices. This implies the Hall condition for H, as H equals A(Q) after the removal of three vertices.

For the proof of Claim B, we need a slight extension of Claim A, namely, that every edge of H takes part in some perfect matching. This can be verified by showing that $V (Q) \setminus \{ s,{s}^{{_\ast}},{t}^{{_\ast}}\}$ is the unique nonempty subset of vertices of Q such that the Hall condition for the set is tight in H. Now we use some facts about α-orientations of planar graphs from [18]:

• Perfect matchings of H are in bijection with orientations of H with $\mathsf{out\text{ -}deg}(x) = 1$ for all x ∈ X and $\mathsf{out\text{ -}deg}(r) =\deg (r) - 1$ for all r ∈ R. We refer to these orientations as α _M -orientations.

• It is possible to move from any α _M -orientation to any other α _M -orientation by flips of the following type: Select an inner face whose boundary is an oriented cycle and revert the orientation of all edges of this cycle. This is true (see [18]) because α _M -orientations have no rigid edges; this follows because every edge takes part in some perfect matching.

Consider two perfect matchings M and M′ of H such that the corresponding α _M -orientations differ by a single flip. Since all the faces of H are quadrangles, the permutations π _M and π _M′ differ by a single transposition, whence $\mathsf{sign}({\pi }_{M}) = -\mathsf{sign}({\pi }_{M^{\prime}})$. To obtain ${\mathsf{sign}}_{S}(M) ={ \mathsf{sign}}_{S}(M^{\prime})$, we need ${\prod \limits }_{ij\in M}{[{A}_{S}]}_{ij} = -{\prod \limits }_{ij\in M^{\prime}}{[{A}_{S}]}_{ij}$. Since all entries of A _S are + 1 or − 1, it is enough to show that if we multiply the four entries of A _S associated with the four edges of a face of H, the result will always be − 1. A face of H is a cycle of the form $({x}_{1},{r}_{1},{x}_{2},{r}_{2})$ with x _i  ∈ X and r _j  ∈ R. In Q we have the edge ${r}_{1}{r}_{2}$, which is oriented in the separating decomposition S, say as ${r}_{1} \rightarrow {r}_{2}$. From the definition of the equations based on S, we find that ${[{A}_{S}]}_{{r}_{1}{x}_{1}} = -{[{A}_{S}]}_{{r}_{1}{x}_{2}}$ and ${[{A}_{S}]}_{{r}_{2}{x}_{1}} = {[{A}_{S}]}_{{r}_{2}{x}_{2}}$. From this we obtain ${\prod \limits }_{ij=1,2}{[{A}_{S}]}_{{r}_{i}{x}_{j}} = -1$. Since we can move between any two matchings with flips and since flips leave the sign unaffected, we have proved Claim B. □ 

The theorem tells us that the linear system (2) has a unique solution x _S . The solution, however, need not be nonnegative. What we do next is to show that based on a solution x _S containing negative entries, we can modify S to obtain a new separating decomposition S′ such that the solution x _S′ of the system corresponding to S′ is nonnegative.

Consider a rectangular dissection R representing S and color gray all rectangles whose value in the solution vector x _S is negative. Let $\Gamma$ be the boundary of the gray area in R. Here is a simple but useful lemma.

Lemma 4.3.

The boundary $\Gamma$ contains no complete segment.

Proof.

Suppose $\Gamma$ contains the complete segment corresponding to a vertex v of Q. Then we have ${x}_{a} < 0$ for all $a \in {\mathcal{F}}_{r}(v)$ and ${x}_{a} \geq 0$ for all $a \in {\mathcal{F}}_{b}(v)$ or the converse. In either case, we get a contradiction because the entries of x _S satisfy Eq. (1). □ 

Let s ₀ be any segment that contributes to $\Gamma$. From the lemma we know that at some interior point of segment s ₀ the boundary snaps off and continues on another segment s ₁. Again, the boundary has to leave s ₁ at some interior point to continue on s ₂. Because this procedure always follows the boundary of the gray region, it has to turn back to segment s ₀. Figure 20 shows an example.

Fig. 20

The separating decomposition S corresponds to the rectangular layout R. In the solution x _S of ${A}_{S} \cdot x ={ \mathbf{e}}_{\mathbf{1}}$, the gray rectangles are those with a negative value. The boundary $\Gamma$ consists of a single cycle whose reversal yields S′. The dissection R′ corresponding to S′ can be squared; small numbers are multiples of the entries of the solution x _S′

Recall that a 2-orientation of a quadrangulation with white and black vertices is an orientation of the edges such that the two black vertices s and t on the outer face have out-degree 0 and all the other vertices have out-degree 2. In [11] it was shown that separating decompositions and 2-orientations of Q are in bijection. Reverting a directed cycle in a 2-orientation yields another 2-orientation.

Now $\Gamma$ corresponds to some directed cycles in S reverting the cycles yields another 2-orientation and via the bijection another separating decomposition S′.

Lemma 4.4.

Let S′ be obtained from the separating decomposition S by reverting the cycles of the boundary $\Gamma$ between faces with positive and negative x _S values. There are no negative entries in the solution vector x _S′ of the system ${A}_{S^{\prime}} \cdot x ={ \mathbf{e}}_{\mathbf{1}}$.

Proof.

Let O be a 2-orientation of a quadrangulation Q and let C be a directed cycle in O. Let O′ denote the 2-orientation obtained from O by reverting C. The relation between the separating decompositions S and S′ corresponding to O and O′ was investigated in [20]. There it is shown that all edges outside the cycle keep their color while all edges in the interior of the cycle change their color. □ 

Now consider the matrices A _S and A _S′ . The rows correspond to the outer vertex t and the inner vertices of Q, and the columns correspond to bounded faces of Q. An entry a _{v, f} is nonzero, more precisely ${a}_{v,f} = \pm 1$, if v is a boundary vertex of f. Only the sign of an entry depends on the separating decomposition; it is positive if f belongs to ${\mathcal{F}}_{r}(v)$ (the set of faces incident to v in the angle between the two outgoing edges of v where incoming edges are red) and it is negative if f belongs to ${\mathcal{F}}_{b}(v)$.

From the above it follows that if f is inside C and v is incident to f, then f belongs to ${\mathcal{F}}_{b}(v)$ with respect to S if and only if f belongs to ${\mathcal{F}}_{r}(v)$ with respect to S′. In other words, if A _S  = (a _{v, f} ) and ${A}_{S^{\prime}} = ({a^{\prime}}_{v,f})$, then

$${a^{\prime}}_{v,f} = \left\{\begin{array}{@{}l@{\quad }l@{}} -{a}_{v,f}\quad &f\ \text{ inside of}\ C \\ {a}_{v,f}\quad &\mbox{ otherwise.} \end{array} \right.$$

The solution x _S′ of ${A}_{S^{\prime}} \cdot x ={ \mathbf{e}}_{\mathbf{1}}$ can, therefore, be obtained from the solution x _S of ${A}_{S} \cdot x ={ \mathbf{e}}_{\mathbf{1}}$ by changing the sign of all entries of x _S that correspond to faces f inside C.

Since S′ was obtained by reversing the boundary enclosing all negative faces of x _S , it follows that x _S′ is nonnegative. □ 

Given a nonnegative solution, it remains to actually construct the squaring with the given sizes. We omit the details but note that the squaring can be constructed using a weighted variant of the algorithm in Sect. 3.2.2.

The electricity approach to squarings implies that to a rectangular dissection there corresponds a unique squaring. This must be the same as the squaring that we obtain by following the approach of this subsection.

There is again the issue of squares of size 0. If we color faces of S corresponding to zero squares gray and consider the boundary $\Gamma$ of the gray region, then Lemma 4.3 holds again. Hence, again, a cycle of $\Gamma$ is a directed cycle in S. Looking at the square representation, we see that a region of zero squares is incident to at most four nonzero squares. A cycle in $\Gamma$ must therefore be of length at most 4. As a consequence, we get

Proposition 4.5.

If Q contains no separating 4-cycle, then the square dissection contains a segment contact representation of Q [we have to allow that two horizontal (resp., vertical) segments share an endpoint].

4.3 Trapezoidal Dissections and Markov Chains

The connection between square dissections and electrical networks was used by Dehn [9] in 1903 to show that if an A ×B rectangle admits a squaring using finitely many squares, then A ∕ B is rational. Tutte used network methods in his investigations of dissections using equilateral triangles [56]. In [50] dissections into triangles are constructed using a generalized ”unsymmetrical” electricity. Since there is a well-known connection between electrical networks and random walks (see e.g. [14]), it is consequent to base the construction of dissections on random walks. This approach has been taken by Kenyon [30].

For the description of Kenyon’s ideas, it is convenient to start with a tiling of a rectangle into trapezoids with horizontal upper and lower sides, known as a trapezoidal dissection. With a trapezoidal dissection $\mathcal{T}$, associate the t-visibility graph ${G}_{\mathcal{T}}$: The vertices of ${G}_{\mathcal{T}}$ are the horizontal segments of the dissection, and the edges of ${G}_{\mathcal{T}}$ correspond to the trapezoids of $\mathcal{T}$. The lower and upper segments of the enclosing rectangle are denoted s and t. An example is shown in Fig. 21.

Fig. 21

A trapezoidal dissection $\mathcal{T}$ and its t-visibility graph ${G}_{\mathcal{T}}$

For a trapezoid T whose horizontal sides are on segments i and j, we let $\mathsf{height}(T)$ be the distance between segments i and j and ${\mathsf{width}}_{i}(T)$ be the length of the side of T contained in segment i; note that ${\mathsf{width}}_{i}(T) = 0$ is possible. Define an unsymmetrical weighting on edges: $m(i,j) = \frac{{\mathsf{width}}_{i}(T)} {\mathsf{height}(T)}$. These weights are used to define a random walk (Markov chain) on ${G}_{\mathcal{T}}$ by taking the probability p(i, j) of a transition from i to j proportional to m(i, j); i.e., $p(i,j) = \frac{1} {{\sum \limits }_{j}m(i,j)}m(i,j)$.

Consider a stationary distribution π of p, that is, a distribution such that for all i:

$$\pi (i) ={ \sum \limits }_{j}\pi (j)p(j,i).$$

In most cases the Markov chain p induced by $\mathcal{T}$ will be aperiodic; in that case p is ergodic and π is unique. For an edge (i, j), define $\pi (i,j) = \pi (i)p(i,j)$ and note that π(i, j) is the probability of the presence of the edge in the random walk. More formally, it is the stationary distribution for the induced random walk on the line graph of ${G}_{\mathcal{T}}$.

Define a function ω on the faces of ${G}_{\mathcal{T}}$ by

• (W₀ ) $\omega ({f}_{\infty }) = 0$, where f _∞ is the outer face.

• (W₁ ) $\omega (f) - \omega (f^{\prime}) = \pi (i,j) - \pi (j,i)$ when (i, j) is an edge with f on the left and f′ on the right side.

Lemma 4.6.

The function w is well defined.

Proof.

First note that if edges (i, j) and (i′, j′) have f on the left and f′ on the right, then the removal of the two edges cuts ${G}_{\mathcal{T}}$ into two components H and H′ each containing at least one vertex. The random walk has to commute in both directions between these components equally often; i.e., $\pi (i,j) + \pi (j^{\prime},i^{\prime}) = \pi (j,i) + \pi (i^{\prime},j^{\prime})$. Therefore, $\omega (f) - \omega (f^{\prime})$ is independent of the edge chosen for the definition. □ 

The value of ω(f) can be determined by taking a dual path from f _∞ to f. To show that the result is independent of the path, it is enough to show that summing up the differences $\pi (i,j) - \pi (j,i)$ on a dual path around vertex i results in zero. This follows from

$${\sum \limits }_{j}\pi (i,j) ={ \sum \limits }_{j}\pi (j,i).$$

To prove this, note that $\pi (i) = \pi (i){\sum \limits }_{j}p(i,j) ={ \sum \limits }_{j}\pi (i)p(i,j) ={ \sum \limits }_{j}\pi (i,j)$, and because π is the stationary distribution, also $\pi (i) ={ \sum \limits }_{j}\pi (j)p(j,i) ={ \sum \limits }_{j}\pi (j,i)$. □ 

The function ω(x) is the expected relative counterclockwise winding number of the random walk around face x. Clearly, the winding number has to comply with the two properties (W₀) and (W₁), but as shown in the lemma, this determines the function.

For a face $f$ of ${G}_{\mathcal{T}}$, let s _f be the corresponding line segment in $\mathcal{T}$ and define $w(f) = 1/\mathsf{slope}({s}_{f})$ and w(f) = 0 if s _f is vertical. Recall that $m(i,j) ={ \mathsf{width}}_{i}(T)/\mathsf{height}(T)$.

Proposition 4.7.

Up to a scalar factor, the functions w(f) and m(i,j) defined on $\mathcal{T}$ equal the winding number ω(f) and the edge-stationary distribution π(i,j) of the Markov chain.

Proof.

Consider a trapezoid from $\mathcal{T}$ as shown in Fig. 22. Taking the coordinates from there, we have

$$m(i,j)=\frac{{x}_{2}-{x}_{1}} {{y}_{4}-{y}_{1}},\quad m(j,i)=\frac{{x}_{3}-{x}_{4}} {{y}_{4}-{y}_{1}},\quad w(f)=\frac{{x}_{4}-{x}_{1}} {{y}_{4}-{y}_{1}},\quad w(f^{\prime})=\frac{{x}_{3}-{x}_{2}} {{y}_{3}-{y}_{2}} =\frac{{x}_{3}-{x}_{2}} {{y}_{4}-{y}_{1}}.$$

It follows that $w(f) - w(f^{\prime}) = m(i,j) - m(j,i)$. Summing up this equation along the dual cycle around a vertex, we obtain ${\sum \limits }_{j}m(i,j) ={ \sum \limits }_{j}m(j,i)$. This implies that m(i, j) is a scalar multiple of an edge-stationary distribution. In turn from $(\mathrm{{W}}_{0})$ and $(\mathrm{{W}}_{1})$, it follows that the values w(f) are multiples of the winding numbers. □ 

Fig. 22

An example trapezoid

Proposition 4.8.

For a vertex i of ${G}_{\mathcal{T}}$ , let y(i) be the y-coordinate of the corresponding segment in $\mathcal{T}$ and let p(i,j) be as above. For all $i\not\in \{s,t\}$ , the function y is harmonic with respect to p; i.e.,

$$y(i) ={ \sum \limits }_{j}y(j)p(i,j).$$

Proof.

Let ${I}^{+} =\{ j : y(j) > y(i)\}$ and ${I}^{-} =\{ j : y(j) < y(i)\}$ and note that if T _ij is a trapezoid connecting segments i and j, then $\mathsf{height}({T}_{ij}) = y(i) - y(j)$ if j ∈ I ⁻ and $\mathsf{height}({T}_{ij}) = -(y(i) - y(j))$ if j ∈ I ⁺. We now have

$$\begin{array}{llll} y(i) -\sum\limits_{j}y(j)p(i,j)& =&\sum\limits_{j}(y(i) - y(j))p(i,j) \\ & =& \sum\limits_{j\in{I}^{-}}(y(i) -y(j))p(i,j) +\sum\limits_{j\in {I}^{+}}(y(i) -y(j))p(i,j) \\ & =&\frac{1}{\sum\nolimits_{{j}m(i,j)}}\left(\sum\limits_{j\in{I}^{-}}{\mathsf{width}}_{i}({T}_{ij})-\sum\limits_{j\in{I}^{+}}{\mathsf{width}}_{i}({T}_{ij})\right) = 0.\end{array}$$

The last equation follows because the trapezoids with segment i on the low side and those with the segment on the high side can both be used to partition the segment. □ 

From the tiling $\mathcal{T}$, we have obtained a Markov chain p on ${G}_{\mathcal{T}}$ such that $m(i,j) \sim \pi (i,j)$ and w(f) ∼ ω(f) and the y-coordinates of the vertex segments are a function that is p-harmonic for all vertices $i\not\in \{s,t\}$ of ${G}_{\mathcal{T}}$.

To revert the process, let G = (V, E) be a planar graph with s and t on the outer face and let p be a Markov chain on G. From these data, we obtain the edge-stationary distribution $\pi : E \rightarrow \mathsf{IR}$, the winding numbers ω(f) on the faces of G, and the unique p-harmonic function $y : V \rightarrow \mathsf{IR}$ with y(s) = 0 and y(t) = 1.

Note that the probability h(i) that a random walk started at i reaches t before reaching s has the properties required for y(i). Uniqueness, i.e., the fact that h(i) = y(i), follows from the maximum principle for discrete harmonic functions; see, e.g., [3].

From the data, we build a trapezoidal dissection $\mathcal{T}$ such that the trapezoid T _ij corresponding to an edge (i, j) of G with y(i) < y(j) is a horizontal translate of the trapezoid with corners

$$\begin{array}{rcl} (\omega (x)(y(j) - y(i)),y(j)),& & \qquad ((\pi (i,j) + \omega (x^{\prime}))(y(j) - y(i)),y(j)), \\ (0,y(i)),& & \qquad (\pi (i,j)(y(j) - y(i)),y(i)).\end{array}$$

The proof that these trapezoids fit nicely together to a tiling of a rectangle is done inductively. For the organization of the inductive argument, the following lemma is useful.

Lemma 4.9.

The orientation B of G with (i,j) ∈ B iff y(i) < y(j) is a bipolar orientation with source s and sink t.

Proof.

This follows from the maximum principle for discrete harmonic functions, i.e, from the fact that such a function assumes its maximum at boundary vertices. □ 

As with squarings, it may happen that trapezoids degenerate and have zero area. We say that a Markov chain p on G is generic if this does not happen. In particular, this implies that p(i, j) + p(j, i) > 0 for all edges (i, j) of G and y(i)≠y(j) for every pair i, j of adjacent vertices.

Theorem 4.10 (Kenyon ’98). 

Let G be planar with s and t on the outer face. If p is a generic Markov chain on G and $\mathcal{T}$ is the trapezoidal dissection associated with (G,p) by the above construction, then $G = {G}_{\mathcal{T}}$ and p can be recovered from $\mathcal{T}$.

Some special cases are particularly interesting:

• If p is reversible, i.e., if $\pi (i)p(i,j) = \pi (j)p(j,i)$ for all edges, then all trapezoids in the dissection are rectangles. (This is the case of planar electrical networks with edges of varying resistance.)

• If $p(i,j) = \frac{1} {\mathrm{deg}(i)}$, then $\pi (i) = \frac{\mathrm{deg}(i)} {2m}$ and the aspect ratios $m(i,j) \sim \pi (i)p(i,j)$ of all rectangles are equal. Hence, after scaling the dissection, we obtain a squaring.

Kenyon [30] also considers dissections of more general trapezoidal shapes than rectangles. Markov chains that yield dissections into nontrapezoidal shapes are considered in [36].

5 Square Duals

In this section, we review a result of Schramm [49]. He proves the existence of rectangular duals where all rectangles are squares for a large class of triangulations. The approach is based on extremal length. To begin, we need some definitions. Throughout G = (V, E) is a prescribed graph.

• Any function $m : V \rightarrow {\mathsf{IR}}^{+}$ is called a discrete metric on G.

• The length of a path γ in G is ${\mathcal{l}}_{m}(\gamma ) ={ \sum \limits }_{x\in \gamma }m(x)$.

• For $A,B \subset V$, let $\Gamma (A,B)$ be the set of A, B paths.The distance between A and B is defined as ${\mathcal{l}}_{m}(A,B) =\min_{\gamma \in \Gamma (A,B)}{\mathcal{l}}_{m}(\gamma )$.

• The extremal length of A, B is $L(A,B) =\sup_{m}\frac{{\mathcal{l}}_{m}{(A,B)}^{2}} {\vert \vert m\vert {\vert }^{2}} =\sup_{m}\frac{{\mathcal{l}}_{m}{(A,B)}^{2}} {{\sum \limits }_{v}m{(v)}^{2}}$.

• A metric realizing the extremal length is an extremal metric.

Proposition 5.1.

For G and $A,B \subset V$ , there is a (up to scaling) unique extremal metric.

Proof.

If m is extremal, then so is every positive scalar multiple of m. Therefore, we only have to look at metrics m with ${\mathcal{l}}_{m}(A,B) = 1$. □ 

These metrics form a polyhedral set P described by the finitely many linear inequalities of the form ${\sum \limits }_{x\in \gamma }m(x) \geq 1$ with $\gamma \in \Gamma (A,B)$.

The extremal metric is the unique m ∈ P with minimal norm $\vert \vert m\vert \vert = \sqrt{{\sum \limits }_{v}m{(v)}^{2}}$. □ 

Proposition 5.2.

A squaring with A and B representing the top and bottom of the dissection induces an extremal metric on the rectangular dual graph G of the squaring.

Proof.

Let $h = \mathsf{height}(R)$ and $w = \mathsf{width}(R)$. We may assume $h \cdot w = 1$. Let $s : V \rightarrow \mathsf{IR}$ be the metric where s(v) is the side length of the square of vertex v. Since $\vert \vert s\vert {\vert }^{2} = \sum s{(v)}^{2} = h \cdot w = 1$, we have $\vert \vert s\vert \vert = 1$. □ 

Let m be any metric. For t ∈ [0, w], the squaring induces a path γ _t consisting of the vertices v whose representing square is intersected by the vertical line x = t. By definition, ${\mathcal{l}}_{m}(A,B) \leq {\sum \limits }_{v\in {\gamma }_{t}}m(v)$.

$$\begin{array}{rcl} w \cdot l_{m}(A,B)& \leq &{\int\limits }_{0}^{w} \sum\limits_{v\in {\gamma }_{t}}m(v)dt ={\int\limits }_{0}^{w} \sum\limits_{v\in V }m(v){\delta }_{[v\in{\gamma}_{t}]}dt = \sum\limits_{v\in V }m(v){\int \limits}_{0}^{w}{\delta}_{ [v\in {\gamma }_{t}]}dt \\ & =&\sum\limits_{v\in V }m(v)s(v)=\langle m,s\rangle \leq \vert \vert m\vert \vert \cdot \vert \vert\vert \vert = \vert \vert m\vert \vert\\ \end{array}$$

Hence,

$$\frac{{\mathcal{l}}_{m}{(A,B)}^{2}} {\vert \vert m\vert {\vert }^{2}} \leq \frac{1} {{w}^{2}} = {h}^{2} = \frac{{h}^{2}} {\vert \vert s\vert {\vert }^{2}}.$$

This shows that the metric s is extremal. □ 

The proposition, together with the uniqueness of extremal metrics, implies that for a given G, there can, up to scaling, only be a single square dual.

We next show the converse of the proposition: Extremal lengths can be used to get squarings. Let G be an inner triangulation of a 4-gon, i.e., a triangulation with one outer edge removed. Call the four vertices of the outer face s, a, t, b in counterclockwise order.

Now let m be an extremal metric with respect to a and b such that $\vert \vert m\vert \vert = 1$ and define h = l _m (a, b). For an inner vertex v of G, let x(v) be the length of a shortest s → v path and y(v) be the length of a shortest a → v path. The length of a path is, of course, taken with respect to m.

Proposition 5.3 (Schramm ’93). 

The squares ${Z}_{v} = [x(v) - m(v),x(v)] \times [y(v) - m(v),y(v)]$ for inner vertices of G together with four appropriate squares for the outer vertices yield a square contact representation of G in the rectangle $R = [0,{h}^{-1}] \times [0,h]$ . Moreover, if G has no separating 3- and 4-cycles, then there are no degenerate squares; i.e., m(v) > 0 for all v.

Proof.

The first claim is that all edges are represented as contacts or intersections. Let (u, v) be an interior edge of G and u, v≠t. From $x(v) \leq x(u) + m(v)$ and $x(u) \leq x(v) + m(u)$ and the corresponding inequalities for y(u) and y(v), it follows that ${Z}_{u} \cap {Z}_{v}\neq \varnothing$. The same property for edges of the form (u, t) is nontrivial. Schramm [49] has a direct argument, while Lovász [38] argues with blocking polyhedra and shows that m is an extremal metric with respect to s and t. We skip this part of the proof. □ 

The next claim is that the squares cover R; i.e., $R \subseteq {\bigcup }_{v}{Z}_{v}$. Suppose that there is a point p in R that is not contained in a Z _v . For each v, choose a representative point ${q}_{v} \in {Z}_{v}$ and draw the edges of G such that an edge (u, v) is represented by a curve connecting q _u and q _v that stays in ${Z}_{u} \cup {Z}_{v}$. The simplest choice for the edge may be to represent it as union of straight segments $[{q}_{u},{q}_{uv}]$ and $[{q}_{uv},{q}_{v}]$ for some ${q}_{uv} \in {Z}_{u} \cap {Z}_{v}$. With triangle (u, v, w) in G, let T _{(u, v, w)} be the topological triangle enclosed by the edges connecting q _u , q _v , and q _w in R. By following a generic ray starting at p and considering situations where the ray crosses a curve representing an edge, it can be verified that p is contained in an odd number of the triangles T _{(u, v, w)}. Therefore, there is at least one triangle T _{(u, v, w)} covering p. Consider $S = {Z}_{u} \cup {Z}_{v} \cup {Z}_{w}$. The boundary of T _{(u, v, w)} is a closed curve γ contained in S such that $p\not\in S$ is in the interior of γ. Since this is impossible for a union S of three squares, we have a contradiction. This proves the claim.

Since $\mathsf{area}(R) = 1 = \vert \vert m\vert {\vert }^{2} ={ \sum \limits }_{v}m{(v)}^{2} ={ \sum \limits }_{v}\mathsf{area}({Z}_{v})$, it follows that intersections of the squares are confined to their boundaries, and we have a tiling of R with squares. We also know that all edges of G are represented by contacts. With a counting argument, it can be shown that these have to be all contacts between the squares except for

• Additional corner-to-corner contacts at points where four squares meet.

• Contacts where at least one of the two participating squares is a degenerate square of size 0.

This shows that the extremal length yields a square contact representation of G.

Finally, we show that in the absence of separating 3- and 4-cycles, all squares have nonzero area. Let W be the set of vertices of a connected component of the subgraph of G induced by vertices with degenerate squares, i.e., with m(v) = 0. All the vertices of W are represented by the same point p in R. This point p must also be contained in all Z _v , where $v\not\in W$ is a neighbor of some w ∈ W. These at most four vertices v form a cycle separating W from the outer vertices. □ 

5.1 Square Duals and Transversal Structures

We now propose an alternative method to approach the problem of finding a square dual for an inner triangulation of a 4-gon. The approach is similar to what we have done in Sect. 4.2. First, we encode a rectangular dual as a graph with additional structure, in this case a transversal structure. From the transversal structure, we extract a system of linear equations such that a nonnegative solution yields the metric information needed for the square dual. If the solution has negative variables, we do not know how to use the solution to get a square dual. In this respect, the situation is more complicated than in Sect. 4.2. However, the signs in the solution provide a rule for changing the transversal structure. With the new transversal structure, we can proceed as before. Unfortunately, we cannot yet prove that the procedure stops, i.e., that at some iteration the solution is nonnegative and we get the square dual we are looking for.

Let G be an inner triangulation of a 4-gon with outer vertices s, a, t, b in counterclockwise order. A transversal structure for G is an orientation and 2-colorings of the inner edges of G such that

• 1. All edges incident to s, a, t, and b are blue outgoing, red outgoing, blue ingoing, and red ingoing, respectively.

• 2. The edges incident to an inner vertex v come in clockwise order in four nonempty blocks consisting solely of red ingoing, blue ingoing, red outgoing, and blue outgoing edges, respectively.

Transversal structures have been studied in [22, 23, 31]. The relevance of transversal structures in our context comes from the following simple proposition. See Fig. 23.

Fig. 23

The two local conditions and an example of a transversal structure together with a corresponding dissection

Proposition 5.4.

Transversal structures of an inner triangulation G of a 4-gon with outer vertices s,a,t,b are in bijection with combinatorially different rectangular dissections R with rectangular dual $G \setminus \{ s,a,t,b\}$ , where the rectangles of vertices adjacent to s, a, t, and b touch the left, lower, right, and upper boundary of R, respectively.

Based on a transversal structure T, we want to write down a system of linear equations such that a nonnegative solution of the system yields a square dissection with T as the underlying transversal structure. For an inner vertex v, let x _v be a variable intended to represent the size of the square representing v. For a directed edge (u, v) in T, let x _uv be a variable representing the length of the contact between the rectangles representing u and v. The edges incident to a vertex v are partitioned into the four nonempty classes ${\mathcal{R}}^{+}(v)$, ${\mathcal{B}}^{+}(v)$, ${\mathcal{R}}^{-}(v)$, and ${\mathcal{B}}^{-}(v)$, where the letter indicates the color of the edge and the sign denotes whether the edge is outgoing or incoming. With vertex v, we associate four equations:

$$\sum\limits_{(u,v)\in {\mathcal{R}}^{+}(v)}{x}_{uv} ={x}_{v},\quad \sum\limits_{(u,v)\in {\mathcal{B}}^{+}(v)}{x}_{uv} ={x}_{v},\quad \sum\limits_{(v,u)\in {\mathcal{R}}^{-}(v)}{x}_{vu} ={x}_{v},\quad \sum\limits_{(v,u)\in {\mathcal{B}}^{-}(v)}{x}_{vu} ={x}_{v}.$$

To forbid the trivial solution, we require that the width of the enclosing rectangle be 1. This is done by adding the equation ${\sum \limits }_{(u,b)\in {\mathcal{R}}^{-}(b)}{x}_{ub} = 1$. Collecting the coefficients of the equations in a matrix A _T , we find that the vector x of lengths of a square dissection is a solution to the system

$${A}_{T} \cdot x ={ \mathbf{e}}_{\mathbf{1}}.$$

(3)

Fact 1.

If the solution vector x is nonnegative, then there is a square dissection with the lengths given by x. If the solution vector x is positive, the transversal structure corresponding to the square dissection is T.

Fact 2.

The matrix A _T is nondegenerate; hence, there is a unique solution x to the system.

A proof of Fact 2 can be given along the lines of the proof of Theorem 4.2. The idea is to interpret A _T as the adjacency matrix of a planar bipartite graph H. Terms in the Leibniz expansion of $\det ({A}_{T})$ correspond to perfect matchings in H. It can be shown that H admits a perfect matching. Moreover, the sign of all perfect matchings is equal because all inner faces of H have length 10, i.e., have residue 2 modulo 4.

To deal with the case where the solution vector x has negative entries, we need more insight into transversal structures. Recall from Sect. 2.3 the definition of the trimmed angle graph $\check{A}(G)$ associated with a plane graph G. The vertex set of this graph consists of the primal vertex set V together with the dual vertex set save the dual of the unbounded face, i.e., ${V }^{{_\ast}}\setminus \{ {f}_{\infty }\}$. Edges of $\check{A}(G)$ correspond to incidences between vertices and bounded faces of G or equivalently to the internal angles of G. Inner faces of $\check{A}(G)$ correspond to the inner edges of G.

Given a transversal structure T on G, we define an orientation of $\check{A}(G)$ as follows: Orient the edge {v, f} as v → f when the two edges incident to f and v have different colors; otherwise, the edge is oriented f → v. It can be verified that

• $\mathsf{out\text{ -}deg}(v) = 4$ for all inner vertices of G, $\mathsf{out\text{ -}deg}(v) = 0$ for the four vertices of the outer face, and $\mathsf{out\text{ -}deg}(f) = 1$.

An orientation of $\check{A}(G)$ obeying the above rules for the out-degrees is called an α₄-orientation (note that up to changing the role of the color classes, α₄-orientations are identical to the ${\alpha }_{\mathsf{skel}}$ orientations from Sect. 2.3).

Fact 3.

Let G be an inner triangulation of a 4-gon with outer vertices s,a,t,b. Transversal structures of G are in bijection with α ₄ -orientations of $\check{A}(G)$.

Fact 4.

Let x be the solution to the system of equations corresponding to the transversal structure T, and let E ⁻ (x) be the set of edges whose value in x is negative. The boundary ${\partial }^{-}(x)$ of the union of all faces of $\check{A}(G)$ corresponding to edges in E ⁻ (x) decomposes into directed cycles with respect to the α ₄ -orientation corresponding to T.

Reverting a directed cycle in an α₄-orientation yields another α₄-orientation. Hence, reverting all edges of ∂ ⁻(x) yields another α₄-orientation, which corresponds to a new transversal structure T′ of G.

The approach for computing a square dual for G is this:

• Compute a transversal structure T of G and the matrix A _T .

• Compute a solution x _T of ${A}_{T} \cdot x ={ \mathbf{e}}_{\mathbf{1}}$.

If all entries of x _T are nonnegative, we are done; based on x _T , we can build the square dissection for G. If there are negative entries in x _T , we can use the α₄-orientation to transform T into another transversal structure T′ and iterate. We conjecture that independent of the choice of T, the sequence T → T′ → T′ → has a finite length; i.e., there is a k such that the solution ${x}_{{T}^{(k)}}$ of the system corresponding to T ^(k) is nonnegative.

There is strong experimental support for the truth of the conjecture.