A Polynomial Time Algorithm for Finding Area-Universal
Rectangular Layouts

arXiv:1302.3672v7 [cs.CG] 15 Sep 2016

Jiun-Jie Wang
State University of New York at Buffalo, Buffalo, NY 14260, USA.
Email: jiunjiew@buffalo.edu
Abstract
A rectangular layout L is a rectangle partitioned into disjoint smaller rectangles so that no four
smaller rectangles meet at the same point. Rectangular layouts were originally used as floorplans
in VLSI design to represent VLSI chip layouts. More recently, they are used in graph drawing as
rectangular cartograms. In these applications, an area a(r) is assigned to each rectangle r, and
the actual area of r in L is required to be a(r). Moreover, some applications require that we use
combinatorially equivalent rectangular layouts to represent multiple area assignment functions. L
is called area-universal if any area assignment to its rectangles can be realized by a layout that is
combinatorially equivalent to L.
A basic question in this area is to determine if a given plane graph G has an area-universal rectangular layout or not. A fixed-parameter-tractable algorithm for solving this problem was obtained
2
in [4]. Their algorithm takes O(2O(K ) nO(1) ) time (where K is the maximum number of degree 4
vertices in any minimal separation component), which is exponential time in general case. It is an
open problem to find a true polynomial time algorithm for solving this problem. In this paper, we
describe such a polynomial time algorithm. Our algorithm is based on new studies of properties of
area-universal layouts. The polynomial run time is achieved by exploring their connections to the
regular edge labeling construction.

1

Introduction

A rectangular layout L is a partition of a rectangle R into a set R(L) = {r1 , . . . , rn } of disjoint smaller
rectangles by vertical and horizontal line segments so that no four smaller rectangles meet at the same
point. An area assignment function of a rectangular layout L is a function a : R(L) → R+ . We say L is
a rectangular cartogram for a if the area of each ri ∈ R(L) equals to a(ri ). We also say L realizes the
area assignment function a.
Rectangular cartograms were introduced in [14] to display certain numerical quantities associated
with geographic regions. Each rectangle ri represents a geographic region. Two regions are geographically
adjacent if and only if their corresponding rectangles share a common boundary in L. The areas of the
rectangles represent the numeric values being displayed by the cartogram.
In some applications, several sets of numerical data must be displayed as cartograms of the same set
of geographic regions. For example, three ﬁgures in [14] are the cartograms of land area, population, and
wealth within the United States. In such cases, we wish to use cartograms whose underlying rectangular
layouts are combinatorially equivalent (to be deﬁned later). Fig 1 (1) and (2) show two combinatorially
equivalent layouts with diﬀerent area assignments. The following notion was introduced in [4].
Definition 2. A rectangular layout L is area-universal if any area assignment function a of L can be
realized by a rectangular layout that is combinatorially equivalent to L.
A natural question is: which layouts are area-universal? A nice characterization of area-universal
rectangular layouts was discovered in [4]:
1

s

(1)

(2)

(3)

Figure 1: Examples of rectangular layout: (1) and (2) are two combinatorially equivalent layouts with
diﬀerent area assignments. Both are area-universal layouts. (3) A layout that is not area-universal.

Theorem 3. [4] A rectangular layout L is area-universal if and only if every maximal line segment in
L is a side of at least one rectangle in L. (A maximal line segment is a line segment in L that cannot
be extended without crossing other line segments in L.)
In Fig 1, the layouts (1) and (2) are area-universal, but the layout (3) is not. (The maximal vertical
line segment s is not a side of any rectangle.)
For a plane graph G, we say a rectangular layout L represents G if the following hold: (1) The set of
smaller rectangles of L one-to-one corresponds to the set of vertices of G; and (2) two vertices u and v
are adjacent in G if and only if their corresponding rectangles in L share a common boundary. In other
words, if L represents G, then G is the dual graph of small rectangles in L.
Area-universal rectangular layout representations of graphs are useful in other ﬁelds [13]. In VLSI
design, for example [17], the rectangles in L represent circuit components, and the common boundary
between rectangles in L model the adjacency requirements between components. In early VLSI design
stage, the chip areas of circuit components are not known yet. Thus, at this stage, only the relative
positions of the components are considered. At later design stages, the areas of the components (namely,
the rectangles in L) are speciﬁed. An area-universal layout L enables the realization of the area assignments speciﬁed at later design stages. Thus, the ability of ﬁnding an area-universal layout at the early
design stage will greatly simplify the design process at later stages. The applications of rectangular
layouts and cartograms in building design and in tree-map visualization can be found in [2, 1]. Heuristic
algorithms for computing the coordinates of a rectangular layout that realizes a given area assignment
function were presented in [16, 11].
A plane graph G may have many rectangular layouts. Some of them may be area-universal, while
the others are not. Not every plane graph has an area-universal layout. In [15], Rinsma described an
outerplanar graph G and an area assignment to its vertices such that no rectangular layout realizes the
area assignment. Thus it is important to determine if G has an area-universal layout or not. Based
on Theorem 3, Eppstein et al. [4] described an algorithm that ﬁnds an area-universal layout for G if
2
one exists. Their algorithm takes O(2O(K ) nO(1) ) time, where K is the maximum number of degree 4
vertices in any minimal separation component. For a ﬁxed K, the algorithm runs in polynomial time.
However, their algorithm takes exponential time in general case.
In this paper, we describe the ﬁrst polynomial-time algorithm for solving this problem. Our algorithm
is based on studies of properties of area-universal layouts and their connection to the regular edge labeling
construction. The paper is organized as follows. In §2, we introduce basic deﬁnitions and preliminary
results. §3 outlines a Face-Addition algorithm with exponential time that determines if G has an areauniversal rectangular layout. §4 introduces the concepts of forbidden pairs, G-pairs and M-triples that
are extensively used in our algorithm. In §5, we describe how to convert the Face-Addition algorithm
with exponential time to an algorithm with polynomial time.

2

vN
vN
c
b g
vW
h vE
e
a f d
vS

vN
c

b
g

vW

c

b
h

e
a

f

b
g

vE vW

h

e
a

d

vS

(1) Lext

vN

c

(2) Gext

f

d

g

vE vW

h

e
a

f

vS

vS

(3) G1

(4) G2

vE

d

Figure 4: Examples of rectangular layout and REL. (1) Rectangular layout Lext ; (2) The graph
corresponding to Lext with an REL R = {T1 , T2 }; (3) the graph G1 of R; (4) the graph G2 of R.

2

Preliminaries

In this section, we give deﬁnitions and important preliminary results. Deﬁnitions not mentioned here
are standard. A graph G = (V, E) is called planar if it can be drawn on the plane with no edge crossings.
Such a drawing is called a plane embedding of G. A plane graph is a planar graph with a ﬁxed plane
embedding. A plane embedding of G divides the plane into a number of connected regions. Each region
is called a face. The unbounded region is called the exterior face. The other regions are called interior
faces. The vertices and edges on the exterior face are called exterior vertices and edges. Other vertices
and edges are called interior vertices and edges. We use cw and ccw as the abbreviation of clockwise and
counterclockwise, respectively.
For a simple path P = {v1 , v2 , · · · , vp } of G, the length of P is the number of edges in P . P is called
chord-free if for any two vertices vi , vj with |i − j| > 1, the edge (vi , vj ) ∈
/ E. A triangle of a plane graph
G is a cycle C with three edges. C divides the plane into its interior and exterior regions. A separating
triangle is a triangle in G such that there are vertices in both the interior and the exterior of C.
When discussing the rectangular layout L of a plane graph G, we can simplify the problem as follows.
Let a, b, c, d be the four designated exterior vertices of G that correspond to the four rectangles in L
located at the southwest, northwest, northeast and southeast corners, respectively. Let the extended
graph Gext be the graph obtained from G as follows:
1. Add four vertices vW , vN , vE , vS and four edges (vW , vN ), (vN , vE ), (vE , vS ), (vS , vW ) into Gext .
2. Connect vW to every vertex of G on the exterior face between a and b in cw order. Connect vN
to every vertex of G on the exterior face between b and c in cw order. Connect vE to every vertex
of G on the exterior face between c and d in cw order. Connect vS to every vertex of G on the
exterior face between d and a in cw order.
See Figs 4 (1) and (2) for an example. It is well known [12] that G has a rectangular layout L if
and only if Gext has a rectangular layout Lext , where the rectangles corresponding to vW , vN , vE , vS are
located at the west, north, east and south boundary of Lext , respectively. Not every plane graph has
rectangular layouts. The following theorem characterizes the plane graphs with rectangular layouts.
Theorem 5. [12] A plane graph G has a rectangular layout L with four rectangles on its boundary if
and only if:
1. Every interior face of G is a triangle and the exterior face of G is a quadrangle; and
2. G has no separating triangles.

3

A plane graph that satisﬁes the conditions in Theorem 5 is called a proper triangular plane graph.
From now on we only consider such graphs.
Our algorithm relies heavily on the concept of the regular edge labeling (REL) introduced in [9].
RELs have also been studied by Fusy [7, 8], who refers them as transversal structures. REL are closely
related to several other edge coloring structures of planar graphs that can be used to describe straight
line embeddings of orthogonal polyhedra [5, 6].
Definition 6. Let G be a proper triangular plane graph. A regular edge labeling REL R = {T1 , T2 } of
G is a partition of the interior edges of G into two subsets T1 , T2 of directed edges such that:
• For each interior vertex v, the edges incident to v appear in ccw order around v as follows: a set
of edges in T1 leaving v; a set of edges in T2 leaving v; a set of edges in T1 entering v; a set of
edges in T2 entering v. (Each of the four sets contains at least one edge.)
• Let vN , vW , vS , vE be the four exterior vertices in ccw order. All interior edges incident to vN are
in T1 and entering vN . All interior edges incident to vW are in T2 and entering vW . All interior
edges incident to vS are in T1 and leaving vS . All interior edges incident to vE are in T2 and
leaving vE .
Fig 4 (2) shows an example of REL. (The green solid lines are edges in T1 . The red dashed lines
are edges in T2 .) It is well known that every proper triangular plane graph G has a REL, which can
be found in linear time [9, 10]. Moreover, from a REL of G, we can construct a rectangular layout L
of G in linear time [9, 10]. Conversely, if we have a rectangular layout L for G, we can easily obtain a
REL R of G as follows. For each interior edge e = (u, v) in G, we label and direct e according to the
following rules. Let ru and rv be the rectangle in L corresponding to u and v respectively.
• If ru is located below rv in L, the edge e is in T1 and directed from u to v.
• If ru is located to the right of rv in L, the edge e is in T2 and directed from u to v.
The REL R obtained as above is called the REL derived from L. (See Fig 4 (1) and (2)).
Definition 7. Let L1 and L2 be two rectangular layouts of a proper triangular plane graph G. We say
L1 and L2 are combinatorially equivalent if the RELs of G derived from L1 and from L2 are identical.
Thus, the RELs of G one-to-one correspond to the combinatorially equivalent rectangular layouts
of G. We can obtain two directed subgraphs G1 and G2 of G from an REL R = {T1 , T2 } as follows.
• The vertex set of G1 is V . The edge set of G1 consists of the edges in T1 with direction in T1 , and
the four exterior edges directed as: vS → vW , vS → vE , vW → vN , vE → vN .
• The vertex set of G2 is V . The edge set of G2 consists of the edges in T2 with direction in T2 , and
the four exterior edges directed as: vS → vW , vN → vW , vE → vS , vE → vN .
Fig 4 (3) and (4) show the graph G1 and G2 for the REL shown in Fig 4 (2). For each face f1 in
G1 , the boundary of f1 consists of two directed paths. They are called the two sides of f1 . Each side of
f1 contains at least two edges. Similar properties hold for the faces in G2 [7, 8, 9, 10].
Definition 8. A REL R = {T1 , T2 } of G is called slant if for every face f in either G1 or G2 , at least
one side of f contains exactly two directed edges.
Theorem 3 characterizes the area-universal layouts in terms of maximal line segments in L. The
following lemma characterizes area-universal layouts in term of the REL derived from L.
4

c

e
d

f
b

e

c

f
b

d
a

a

(1)

(2)

Figure 10: (1) a fan F(a, b, c) has the back boundary (a, b, c) and the front boundary (a, d, e, f, c); (2) a
mirror fan M(a, f, e) has the back boundary (a, b, c, d, e) and the front boundary (a, f, e).

Lemma 9. A rectangular layout L is area-universal if and only if the REL R derived from L is slant.
Proof: Note that each face in G1 (G2 , respectively) corresponds to a maximal vertical (horizontal,
respectively) line segment in L. (In the graph G1 in Fig 4 (3), the face f1 with the vertices f, e, g, c, h
corresponds to the vertical line segment that is on the left side of the rectangle h in Fig 4 (1)).
Assume L is area-universal. Consider a face f in G1 . Let lf be the maximal vertical line segment
in L corresponding to f . Since L is area-universal, lf is a side of a rectangle r in L. Without loss of
generality, assume r is to the left of lf . Then the left side of the face f consists of exactly two edges.
Thus G1 satisﬁes the slant property. Similarly, we can show G2 also satisﬁes the slant property.
Conversely, assume R is a slant REL. The above argument can be reversed to show that L is
area-universal.
The REL shown in Fig 4 (2) is not slant because the slant property fails for one G2 face. So the
corresponding layout shown in Fig 4 (1) is not area-universal. By Lemma 9, the problem of ﬁnding an
area-universal layout for G is the same as the problem of ﬁnding a slant REL for G. From now on, we
consider the latter problem and G always denotes a proper triangular plane graph.

3

Face-Addition Algorithm with Exponential Time

In this section, we outline a Face-Addition procedure that generates a slant REL R = {T1 , T2 } of
G through a sequence of steps. The procedure starts from the directed path consisting of two edges
vS → vE → vN . Each step maintains a partial slant REL of G. During a step, a face f of G1 is added
to the current graph, resulting in a larger partial slant REL. When f is added, its right side is already
in the current graph. The edges on the left side of f are placed in T1 and directed upward. The edges of
G in the interior of f are placed in T2 and directed to the left. The process ends when the left boundary
vS → vW → vN is reached. With this informal description in mind, we ﬁrst introduce a few deﬁnitions.
Then we will formally describe the Face-Addition algorithm (which takes exponential time).
Consider a face f of G1 added during the above procedure. Because we want to generate a slant
REL R, at least one side of f must be a path of length 2. This motivates the following deﬁnition. Figs
10 (1) and (2) show examples of a fan and a mirror fan, respectively.
Definition 11. Let vl , vm , vh be three vertices of G such that vl and vh are two neighbors of vm and
(vl , vh ) ∈
/ E. Let Pcw be the path consisting of the neighbors {vl , v1 , . . . , vp , vh } of vm in cw order between
vl and vh . Let Pccw be the path consisting of the neighbors {vl , u1 , . . . , uq , vh } of vm in ccw order between
vl and vh . Note that since G has no separating triangles, both Pcw and Pccw are chord-free.
1. The directed and labeled subgraph of G induced by the vertices vl , vm , vh , v1 , . . . , vp is called the fan
at {vl , vm , vh } and denoted by F(vl , vm , vh ), or simply g.
5

• The front boundary of g, denoted by α(g), consists of the edges in Pcw directed from vl to vh
in cw order. The edges in α(g) are colored green.
• The back boundary of g, denoted by β(g), consists of two directed edges vl → vm and vm → vh .
The edges in β(g) are colored green.
• The inner edges of g, denote by γ(g), are the edges between vm and the vertices v 6= vl , vh
that are on the path Pcw . The inner edges are colored red and directed away from vm .
2. The directed and labeled subgraph of G induced by the vertices vl , vm , vh , u1 , . . . , uq is called the
mirror fan at {vl , vm , vh } and denoted by M(vl , vm , vh ), or simply g.
• The front boundary of g, denoted by α(g), consists of two directed edges vl → vm to vm → vh .
The edges in α(g) are colored green.
• The back boundary of g, denoted by β(g), consists of the edges in Pccw directed from vl to vh
in ccw order. The edges in β(g) are colored green.
• The inner edges of g, denote by γ(g), are the edges between vm and the vertices v 6= vl , vh
that are on the path Pccw . The inner edges are colored red and directed into vm .
Both F(vl , vm , vh ) and M(vl , vm , vh ) are called a gadget at vl , vm , vh . We use g(vl , vm , vh ) to denote
either of them. The vertices other than vl and vh are called the internal vertices of the gadget. If a
gadget has only one inner edge, it can be called either a fan or a mirror fan. For consistency, we call it
a fan. We use g0 = F(vS , vE , vN ) to denote the initial fan, and gT = M(vS , vW , vN ) to denote the final
mirror fan. The following observation is clear:
Observation 12. For a slant REL, each face f of G1 is a gadget of G.
The REL shown in Fig 4 (2) is generated by adding the gadgets: F(vS , vE , vN ), F(vS , d, h),
F(f, h, c), M(e, b, vN ), F(vS , f, e), M(vS , vW , vN ). The following lemma is needed later.
Lemma 13. The total number of gadgets in G is at most O(n2 ).
Proof: Let deg(v) denote the degree of the vertex v in G. For each v, there are at most 2 · deg(v) ·
(deg(v)
− 3) gadgets with v as its middle element. Thus the total number of gadgets of G is at most
P
2
v∈V 2 · deg(v) · (deg(v) − 3) = O(n ).
Definition 14. A cut C of G is a directed path from vS to vN that is the left boundary of the subgraph
of G generated during the Face-Addition procedure. In particular, C0 = vS → vE → vN denotes the
initial cut and CT = vS → vW → vN denotes the ﬁnal cut.
Let C be a cut of G. For any two vertices v1 , v2 of C, C(v1 , v2 ) denotes the subpath of C from v1 to
v2 . The two paths C and C0 enclose a region on the plane. Let G|C denote the subgraph of G induced
by the vertices in this region (including its boundary).
Consider a cut C generated by Face-Addition procedure and a gadget g = g(vl , vm , vh ). In order for
Face-Addition procedure to add g to C, the following conditions must be satisﬁed:
A1: no internal vertices of α(g) are in C; and
A2: the back boundary β(g) is contained in C; and
A3: g is valid for C (the meaning of valid will be deﬁned later).

6

If g satisﬁes the conditions A1, A2 and A3, Face-Addition procedure can add g to the current graph
G|C by stitching β(g) with the corresponding vertices on C. (Intuitively we are adding a face of G1 .)
Let G|C ⊗ g denote the new subgraph obtained by adding g to G|C . The new cut of G|C ⊗ g, denoted
by C ⊗ g, is the concatenation of three subpaths C(vS , vl ), α(g), C(vh , vN ).
The conditions A1 and A2 ensure that C ⊗ g is a cut. Any gadget g satisfying A1 and A2 can be
added during a step while still maintaining the slant property for G1 . However, adding such a g may
destroy the slant property for G2 faces. The condition A3 that g is valid for C is to ensure the slant
property for G2 faces. (The REL shown in Fig 4 (2) is not slant. This is because the gadget F(f, h, c)
is not valid, as we will explain later.) This condition will be discussed in §4.
After each iteration of Face-Addition procedure, the edges of the current cut C are always in T1 and
directed from vS to vN . All G1 faces f1 in G|C are complete (i.e. both sides of f1 are in G|C ). Some
G2 faces in G|C are complete. Some other G2 faces f2 in G|C are open. (i.e. the two sides of f2 are not
completely in G|C .)
Definition 15. Any subgraph G|C generated during the execution of Face-Addition procedure is called a
partial slant REL of G, which satisfies the following conditions:
1. Every complete G1 and G2 face in G|C satisfies the slant REL property.
2. For every open G2 face f in G|C , at least one side of f has exactly one edge.
The intuitive meaning of a partial slant REL G|C is that it is potentially possible to grow a complete
slant REL of G from G|C . The left boundary of a partial slant REL R is called the cut associated with
R and denoted by C(R).
Definition 16.
1. PSR(G) denotes the set of all partial slant RELs of G that can be generated by
Face-Addition procedure.
2. G̃ = {g | g is a gadget in a R ∈ PSR(G)}.
Observe that every slant REL R of G is in PSR(G). This is because R is generated by adding a
sequence of gadgets g1 , . . . gT = M(vS , vW , vN ) to the initial gadget g0 = F(vS , vE , vN ). So if we choose
this particular gi during the ith step, we will get R at the end. Thus G has a slant REL if and only if
gT ∈ G̃. Note that Face-Addition procedure works only if we know the correct gadget addition sequence.
Of course, we do not know such a sequence. The Face-Addition algorithm, described in Algorithm 1,
generates all members in PSR(G).
Algorithm 1: Face-Addition algorithm with Exponential Time
1.1
1.2
1.3

1.4
1.5
1.6

Initialize G̃ = {g0 }, and PSR(G) = {G|α(g0 ) };
repeat
Find a gadget g of G and an R ∈ PSR(G) such that the conditions A1, A2 and A3 are
satisﬁed for g and C = C(R);
Add g into G̃, and add the partial slant REL R ⊗ g into PSR(G);
until no such g and R can be found;
G has a slant REL if and only if the ﬁnal gadget gT ∈ G̃;
Because |PSR(G)| can be exponentially large, Algorithm 1 takes exponential time.

4

Forbidden Pairs, G-Pairs, M-Triples, Chains and Backbones

In this section, we describe the conditions for adding a gadget to a partial slant REL R ∈ PSR(G),
while still keeping the slant REL property for G2 faces. (In other words, the condition A3.)
7

4.1

Forbidden Pairs

Consider a R ∈ PSR(G) and its associated cut C = C(R). Let e be an edge of C. We use open-face(e)
to denote the open G2 face in G|C with e as its open left boundary. The type of open-face(e) speciﬁes
the lengths of the lower side Pl and the upper side Pu of open-face(e):
• Type (1,1): length(Pl ) = 1 and length(Pu ) = 1.
• Type (1,2): length(Pl ) = 1 and length(Pu ) ≥ 2.
• Type (2,1): length(Pl ) ≥ 2 and length(Pu ) = 1.
• Type (2,2): length(Pl ) ≥ 2 and length(Pu ) ≥ 2.
Note that the type of every open G2 face in a partial slant REL cannot be (2, 2). Based on the
properties of REL, we have the following (see Fig 18):
Observation 17. Let R ∈ PSR(G) and e be an edge on C(R).
• If e is the last edge of α(g) of a fan or a mirror fan g, the type of open-face(e) is (2,1).
• If e is a middle edge of α(g) of a fan g, the type of open-face(e) is (1,1).
• If e is the first edge of α(g) of a fan or a mirror fan g, the type of open-face(e) is (1,2).

(2, 1)

(2, 1)

(1, 1)
(1, 1)
(1, 2)

(1, 2)
a

(1)

(2)

Figure 18: The types of open G2 faces: (1) Faces deﬁned by edges on the front boundary of a fan; (2)
Faces deﬁned by edges on the front boundary of a mirror fan.
Definition 19. A pair (g, g ′ ) of two gadgets of G is called a forbidden pair if either (1) the first edge of
β(g) is the last edge of α(g ′ ); or (2) the last edge of β(g) is the first edge of α(g ′ ).
Lemma 20. If a partial REL R contains a forbidden pair (g, g′ ), then R is not slant.
Proof: Case 1: Suppose the ﬁrst edge e1 of β(g) is the last edge of α(g ′ ) (see Fig 21 (1)). Let e2 be
the ﬁrst edge of α(g). The type of open-face(e1 ) is (2, 1) (regardless of whether g′ is a fan or a mirror
fan). Note that open-face(e2 ) extends open-face(e1 ). The length of the upper side of open-face(e1 ) is
increased by 1. Thus the type of open-face(e2 ) is (2, 2) and the slant property for G2 face fails.
Case 2: Suppose the last edge e1 of β(g) is the ﬁrst edge of α(g ′ ) (see Fig 21 (2)). Let e2 be the last
edge of α(g). The type of open-face(e1 ) is (1, 2) (regardless of whether g′ is a fan or a mirror fan). Note
that open-face(e2 ) extends open-face(e1 ). The length of the lower side of open-face(e1 ) is increased by
1. Thus the type of open-face(e2 ) is (2, 2) and the slant property for G2 face fails.
In the REL R shown in Fig 4 (2), (F(f, h, c), F(vS , d, h)) is a forbidden pair. So R is not a slant
REL.

8

(2, 1)

1

2



2

(2, 1)

e1 (1, 2)

(1, 1)

g

(1, 1)



(1, 2)
a

(2)

(1)

Figure 21: The proof of Lemma 20: (1) g is a fan; (2) g is a mirror fan.

4.2

The Condition A3

The following lemma speciﬁes a necessary and suﬃcient condition for adding a fan into G̃, and a suﬃcient
condition for adding a mirror fan into G̃.
Lemma 22. Let R ∈ PSR(G) and C = C(R) be its associated cut. Let g L be a gadget and L = β(g L ).
Suppose that the conditions A1 and A2 are satisfied for gL and C.
1. A fan gL can be added to R (i.e. g L satisfies the condition A3) if and only if there exists a gadget
g R ∈ R such that β(g L ) ⊆ α(g R ).
2. A mirror fan gL can be added to R (i.e. g L satisfies the condition A3) if there exists a gadget
g R ∈ R such that β(g L ) ⊆ α(g R ).

e4

e3

e4

e''
e2

gL

(2, 1)
e' (1, 1)
gR

e1

e''
e''

e3

(2, 1)

(1, 1)
(1, 2)

(1)

a

e2

e'

e1

gO

gU

(2, 1)

e2 (1, 1) R
g

gR

gL

e3

gL

(2, 1)

ek

e''

e'
(1, 2)

e1

(1, 1)
gB
(1, 2)

e'

e1

(1, 1)

a

(3)

(2)

a

(4)

Figure 23: (1) and (2) open faces deﬁned by edges on the front boundary of a fan g L ; (3) and (4) open
faces deﬁned by edges on the front boundary of a mirror fan g O .
Proof: If part of (1): Suppose there exists a gadget gR ∈ R such that β(g L ) ⊆ α(gR ). (Figs 23 (1) and
(2) show two examples. In Fig 23 (1), gR is a fan. In Fig 23 (2), gR is a mirror fan). Let e1 , . . . , ek be
the edges in α(g L ). Let e′ , e′′ be the two edges in β(g L ). Let C ′ = C ⊗ g L be the new cut after adding
gL . For each 2 ≤ i ≤ k − 1, the type of open-face(ei ) is (1, 1).
• open-face(e1 ) extends open-face(e′ ), and add 1 to the length of the upper side of open-face(e′ ).
9

• open-face(ek ) extends open-face(e′′ ), and add 1 to the length of the lower side of open-face(e′′ ).
Regardless of where e′ , e′′ are located on α(gR ), and regardless of whether g R is a fan (see Fig 23
(1)) or a mirror fan (see Fig 23 (2)), the type of open-face(e1 ) is (1, 2); and the type of open-face(ek ) is
(2, 1). Thus R ⊗ g L ∈ PSR(G).
Only if part of (1): Suppose that there exists no gadget gR ∈ R such that β(gL ) ⊆ α(gR ). Let e′ , e′′
be the two edges of β(g L ). e′ must be on the front boundary of some gadget g′ in R. e′′ must be on
the front boundary of some gadget g′′ in R. Clearly g ′ 6= g′′ . (If g′ = g′′ , we would have β(g L ) ⊆ α(g′ )).
Then either (g L , g′ ) or (g L , g ′′ ) must be a forbidden pair. By Lemma 20, gL cannot be added to R.
(2) Let gL be a mirror fan. Suppose there exists a gadget gR ∈ R such that β(gO ) ⊆ α(gR ) (see Fig
23 (3)). Similar to the proof of the if part of (1), we can show R ⊗ g L ∈ PSR(G).
By Lemma 22, the only way to add a fan g L to R is by the existence of a gadget g R ∈ R such that
⊆ α(gR ). For a mirror fan g, there is another condition for adding g to R which we discuss next.
Let v1 = vS , v2 , . . . , vt−1 , vN be the vertices of C = C(R) from lower to higher order. Let e1 and et
be the ﬁrst and the last edge of C. Imagine we walk along C from vS to vN . On the right side of C, we
pass through a sequence of gadgets in R whose front boundary (either a vertex or an edge) touches C.
Let support(R) = (g1 , g2 , . . . , gk−1 , gk ), where e1 ∈ α(g1 ) and et ∈ α(gk ), denote this gadget sequence.
Note that some gadgets in support(R) may appear multiple times in the sequence. (See Fig 26 (1) for
an example.)
Consider a mirror fan g O to be added to R. Note that L = β(g O ) is a subsequence of C. Let a and
b be the lowest and the highest vertex of L. Let el be the ﬁrst edge and eh be the last edge of L. When
walking along L from a to b, we pass through a subsequence of the gadgets in support(R) on the right
of L. Let support(L, R) = (g B = gp , gp+1 , . . . , gq−1 , gq = gU ) denote this gadget subsequence, where:
β(gL )

• g B is the gadget such that el ∈ α(gB ).
• g U is the gadget such that eh ∈ α(gU ).
In Fig 26 (1), if we add a mirror fan g3 with L = β(g3 ) = (a, b, f, h, k, d), then support(L, R) =
(g1 , g0 , g2 ).
Lemma 24. Let R ∈ PSR(G) and C = C(R) be its associated cut. Let g O be a mirror fan and
L = β(g O ). Suppose that the conditions A1 and A2 are satisfied for g O and C. Let support(L, R) =
(gB , gp+1 , · · · , gq−1 , gU ). Then gO can be added to R (i.e. gO satisfies the condition A3) if and only if
neither (gO , gB ) nor (g O , gU ) is a forbidden pair.
Proof: First suppose that gO can be added to R to form a larger partial slant REL. Then, by Lemma
20, neither (gO , gB ) nor (gO , g U ) is a forbidden pair. Conversely, suppose that neither (g O , gB ) nor
(gO , g U ) is a forbidden pair. Let e1 , . . . , ek be the edges of L. The type of open-face(e1 ) is either (1, 1)
or (1, 2). The type of open-face(ek ) is either (1, 1) or (2, 1). (Fig 23 (4) shows an example.) Let e′ , e′′
be the two edges in α(gO ). After adding gO to R, the types of open-face(e′ ) and open-face(e′′ ) becomes
(1, 2) and (2, 1), respectively. They still keep the slant property for G2 faces. Moreover, for each edge
ei (2 ≤ i ≤ k − 1), open-face(ei ) becomes a valid complete G2 face after adding g O to R. Hence R ⊗ gO
is a partial slant REL of G.

4.3

Connections, Chains and Backbones

Given an R ∈ PSR(G) and a gadget g, it is straightforward to check if the conditions in Lemmas 22 and
24 are satisﬁed. However, as described before, maintaining the set PSR(G) requires exponential time.
So we must ﬁnd a way to check the conditions in Lemmas 22 and 24 without explicit representation of
R.
10

i

g5
2

g4

g7
j

k

VN

i

C(h, i)

g6

g8

f
VE

C(c, f)

e
d

g2

VE

k
c
g3

f

g1

e

h

g5

O1

g2
g0

g4 g
1
g3

b

(1)

h

g0

d
a

c

(2)

VS

b
a

Figure 26: (1) R ∈ PSR(G) is obtained by adding gadgets g1 , g2 , g3 , g4 , g5 , g6 , g7 , g8 , in this order, to
g0 . C(R) = (vS , a, c, d, e, j, i, vN ); support(R) = (g0 , g1 , g3 , g2 , g8 , g7 , g5 , g4 , g0 ) and (g0 C g1 C g3 C
g2 C g8 C g7 C g5 C g4 C g0 ). The pair (g0 , g1 ) belongs to the G-pair Λ1 = (g1 , g0 ), the
triple (g1 , g3 , g2 ) belongs to the M-triple Λ2 = (g1 , g3 , g2 ), the triple (g2 , g8 , g7 ) belongs to the M-triple
Λ3 = (g2 , g8 , g7 ), the pair (g7 , g5 ) belongs to the M-triple Λ4 = (g6 , g7 , g5 ), the pair (g5 , g4 ) belongs
to the G-pair Λ5 = (g5 , g4 ) and the pair (g4 , g0 ) belongs to the G-pair Λ6 = (g4 , g0 ). (2) The G-pair
Λ = (g1 , g0 ) is a fractional connection with two pockets: O1 is bounded by C(c, f ) and α(Λ)(c, f ) and
O2 is bounded by C(h, i) and α(Λ)(h, i).
Consider two R, R′ ∈ PSR(G) such that R =
6 R′ but support(R) = support(R′ ). Clearly this implies
C(R) = C(R′ ). By Lemmas 22 and 24, a gadget g can be added to R if and only if g can be added to R′ .
Thus, whether g can be added to an R ∈ PSR(G) is completely determined by the structure of gadgets
in support(R). There may be exponentially many R′ ∈ PSR(G) with support(R′ ) = support(R).
Instead of keeping information of all these R′ , we only need to keep the information of the structure of
support(R). This is the main idea for converting Algorithm 1 to a polynomial time algorithm. In order
to describe the structure of support(R), we need the following terms and notations.
Definition 25. Let R ∈ PSR(G) and g be a gadget with L = β(g).
• If support(L, R) contains only one gadget g R , and the conditions A1, A2 and A3 are satisfied, then
(g, g R ) is called a G-pair. We use (gL , gR ) to denote a G-pair.
• If support(L, R) contains at least two gadgets, and the conditions A1, A2 and A3 are satisfied,
then (g B , g, gU ) is called a M-triple. We use (gB , gO , gU ) to denote a M-triple.
• A G-pair (gL , gR ) or a M-triple (gB , gO , gU ) is called a connection and denoted by Λ.
L , v L ), g R = g(v R , v R , v R ), the front bound• For a connection Λ = (g L , gR ), where gL = g(vlL , vm
m h
l
h
L
R
ary of Λ, denoted by α(g , g ) or α(Λ), is the concatenation of the paths α(gR )(vlR , vlL ), α(gL ),
α(gR )(vhL , vhR ).
B , v B ), g O = g(v O , v O , v O ), g U =
• For a connection Λ = (g B , gO , g U ), where gB = g(vlB , vm
m h
l
h
B
O
U
U
U
g(vl , vm , vh ), the front boundary of Λ, denoted by α(g , g , gU ) or α(Λ), is the concatenation
of the paths α(g B )(vlB , vlO ), α(gO ), α(gU )(vhO , vhU ).

It is tempting to think that if all gadgets in support(R) have been added into G̃, then R has
been constructed. Unfortunately, this is not true. In order to form R, the gadgets in support(R) =
11

(g1 , g2 , . . . , gk−1 , gk ) must have been added to G̃ in the following way: When walking along C(R) from vS
to vN , the gadgets in support(R) form a sequence (Λ1 , . . . , Λp ) of connections such that each consecutive
pair (gi , gi+1 ) or triple (gi−1 , gi , gi+1 ) of gadgets belong to a Λj (1 ≤ j ≤ p); and each consecutive pair
Λi , Λi+1 share a common gadget in support(R). (See Fig 26 (1) for an illustration).
Note that when the pair (gi−1 , gi ) and the pair (gi , gi+1 ) belong to the same connection Λj , it means
gi−1 and gi+1 are the same gadget and (gi , gi+1 ) = (gi , gi−1 ) is a G-pair. In this case, we keep only one Λj
in the sequence Λ1 . . . , Λp . As seen in Fig 26 (1), in addition to these connections Λj (1 ≤ j ≤ p), some
gadget pairs (or triples) that are not consecutive in support(R) may also form additional connections.
(In Fig 26 (1), the gadgets g0 and g2 are not consecutive in support(R). But they form a G-pair (g2 , g0 )).
Let Con(R) denote the set of connections formed by the gadgets in support(R). (By this deﬁnition,
each Λ ∈ Con(R) has at least two gadgets in support(R)). It is the structure of Con(R) that determines
if a new gadget g can be added to R or not. In general, the connections in Con(R) cannot be described
as a simple linear structure. To describe it precisely, we need the following deﬁnitions.
Consider a connection Λ ∈ Con(R). If α(Λ)∩C is a contiguous subpath of C, Λ is called a contiguous
connection. If not, Λ is called a fractional connection. (In Fig 26 (1), the G-pair (g1 , g0 ) is a fractional
connection. Because the cut C ∩ α(g1 , g0 ) are (a, b, c) and (f, h) and (i, k), they are not a contiguous
subpath of C.) Consider a fractional connection Λ. Let u and v be the lowest and the highest vertices
of C ∩ α(Λ) respectively. When walking along C from u to v, we encounter α(Λ) multiple times.
The subpath C(u, v) can be divided into a number of subpaths that are alternatively on α(Λ), not on
α(Λ), . . ., on α(Λ). There exist at least two vertices a, b in α(Λ) such that C(a, b) ∩ α(Λ)(a, b) = {a, b}.
For each such pair of vertices a, b, the interior region bounded by the subpaths C(a, b) and α(Λ)(a, b)
is called a pocket, denoted by O = (C(a, b), Λ), of Con(R). Fig 26 (2) shows a fractional connection Λ
(the G-pair (g1 , g0 )) with two pockets O1 and O2 .
A connection Λ ∈ Con(R) is called maximal if it is not contained in any pocket of Con(R). A
maximal connection can be either contiguous or fractional. A non-maximal connection Λ′ ∈ Con(R)
is either completely contained in some pocket O formed by a subpath of C and a maximal fractional
connection Λ (namely all gadgets of Λ′ are contained in O); or partially contained in O (namely some
gadget of Λ′ is contained in O and some gadget of Λ′ is shared with Λ). (In Fig 26 (2), the G-pair (g3 , g1 )
and the M-triple (g1 , g2 , g0 ) are partially contained in the pocket O1 . The M-triple (g4 , g5 , g2 ) and the
G-pair (g4 , g3 ) are completely contained in O1 ). Note that a pocket may contain other smaller pockets.
In general, the pockets of Con(R) are nested in a forest-like structure.
The way to deal with fractional connections is very similar to contiguous connections. Hence in the
following paragraphs, we will assume there are no fractional connections.
Definition 27. Let two gadgets {g, g ′ } belong to a connection Λ. We say g precedes g ′ on C and write
g C g′ if the following conditions hold: (1) ((α(g) ∩ C) ∪ (α(g′ ) ∩ C)) is contiguous on C; (2) When
walking along C, we encounter the gadget g before g′ .
Depending on the types of connections and their positions on a cut C, there are ﬁve cases for the
relation C . (They are shown in Fig 28.)
Definition 29. Given a partial slant REL R with its associated cut C, a sequence of gadgets (g1 , g2 , · · · , gk )
in support(R) is called a chain of C and denoted by chain(C) if the following conditions hold:
1. (g1 C g2 C · · · C gk ) and
2. for each 1 ≤ i ≤ k − 1, either (gi , gi+1 ) or (gi , gi+1 , gi+2 ) belongs to a connection Λ ∈ Con(R).
In Fig 26 (1), (g0 C g1 C g3 C g2 C g8 C g7 C g5 C g4 C g0 ) is a chain of C where we
have the G-pair (g1 , g0 ), the M-triple (g1 , g3 , g2 ), the M-triple (g2 , g8 , g7 ), the M-triple (g6 , g7 , g5 ), the
G-pair (g5 , g4 ) and the G-pair (g4 , g0 ).
Because the way a partial slant REL R is constructed, the following property is clear.
12

gU
gR

gU

gU

gL
gO

gO

g
gB

gB

(1)

gB

gR

gL

(2)

(3)

(4)

(5)

Figure 28: (1) Case 1: (g L , gR ) is a G-pair and gL C gR ; (2) Case 2: (gL , gR ) is a G-pair and gR C gL ;
(3) Case 3: (gB , g O , gU ) is a M-triple and gB C gO C g U ; (4) Case 4: (gB , gO , gU ) is a M-triple and
gO C g U ; (4) Case 5: (g B , gO , gU ) is a M-triple and g B C gO .

Property 30. Given a partial slant REL R with its associated cut C, the support(R) = (g1 , g2 , · · · , gk )
is a chain of C.
Given a partial slant REL R with its associated cut C, if we can add a gadget g to R, then it implies
that back boundary L = β(g) of g is a part of C. Let support(L, R) be a subsequence of support(R)
consisting of gadgets in support(R) that touch L. We can deﬁne an order L which is similar to C .
Definition 31. Given a mirror fan gO with L = β(g O ), let two gadgets {g, g ′ } belong to a connection Λ.
We say g precedes g′ on L and write g L g′ if the following conditions hold: (1) (α(g) ∩ L) ∪ (α(g ′ ) ∩ L)
is contiguous on L; (2) When walking along L, we encounter the gadgets g before g′ .
Definition 32. Let g O be a mirror fan with L = β(g O ). A backbone(L, R) consists of a sequence of
gadgets (g1 = gB , g2 , · · · , gk = gU ) in support(L, R) such that
1. (g1 L g2 L · · · L gk ),
2. for each 1 ≤ i ≤ k − 1, either (gi , gi+1 ) or (gi , gi+1 , gi+2 ) belongs to a connection Λ ∈ Con(R) and
3. Neither (gO , gB ) nor (g O , g U ) is a forbidden pair.
In Fig 26 (1), consider the mirror fan g3 with L = β(g3 ). We have: support(L) = (g1 , g0 , g2 ) where
Λ1 is the G-pair (g1 , g0 ), Λ2 is the G-pair (g2 , g0 ) and g1 L g0 L g2 .
Based on above discussion, we can restate Lemma 24 as follows:
Lemma 33. Let R ∈ PSR(G) and C = C(R). Let g O be a mirror fan with L = β(gO ). Suppose
that the conditions A1 and A2 are satisfied for gO and C. Let support(L, R) = (g B , gp+1 , · · · , gq−1 , gU ).
Then (gB , gO , gU ) forms a M-triple (i.e. gO satisfies the condition A3) if and only if there exists
a backbone(L, R) consisting of gadgets in support(L, R) and connections in Con(R). Note that each
gadget and connection in backbone(L, R) belong to the same partial slant REL R.

5

Face-Addition Algorithm with Polynomial Time

We will present our polynomial time Face-Addition algorithm in this section. In §5.1, we will describe
the algorithm to ﬁnd a superset of chains. In §5.2, we will give more details of key procedures in §5.1. In
§5.3, we will present an example that Algorithm 2 may combine two subchains of two diﬀerent partial
13

RELs into a chain which only satisﬁes the order C in Property 30 (there exist gadgets coming from
diﬀerent chains). In §5.4, we will describe a backtracking algorithm to check whether whether a chain
in the superset of chains constructed by Algorithm 2 corresponds to a slant REL or not. Also, we will
give runtime analysis of the backtracking algorithm.

5.1

Polynomial Time algorithm

The polynomial time Face-Addition algorithm is described in Algorithm 2.
Algorithm 2: Face-Addition Algorithm with Polynomial Time
Input: A proper triangular plane graph G
2.1 Set Ṽ = {g0 = F(vS , vE , vN )} and V̂ = ∅;
2.2 repeat
2.3
Find a gadget g such that:
either: there exist v-G-pairs (g, gR ) ∈
/ V̂ with gR ∈ Ṽ (v-G-pairs are deﬁned later);
add g into Ṽ (if it’s not already in Ṽ); add all such v-G-pairs (g, gR ) into V̂;
or: g is a mirror fan and there exist v-M-triples (gB , g, gU ) 6∈ V̂ with gB , gU ∈ Ṽ (v-M-triples are
deﬁned later);
add g into Ṽ (if it’s not already in Ṽ); add all such v-M-triples (gB , g, g U ) into V̂;
2.4
2.5
2.6
2.7
2.8

2.9

until no such gadget g can be found;
if gT = M(vS , vW , vN ) is not in Ṽ then
G has no slant REL;
else
Backtrack each v-chain of gT (v-backbone of gT ) to check whether G corresponds a slant
REL in Algorithm 4;
end

Algorithm 2 emulates the operations of Algorithm 1 without explicitly maintaining the set PSR(G).
Instead, it keeps two sets: (1) a set Ṽ of gadgets of G which contains the gadgets in the set G̃ deﬁned in §3,
and (2) a set V̂ of connections of G which contains the connections in the set {Con(R)|R ∈ PSR(G)}
deﬁned in §4.3. In §4.3, many concepts (cut, chain, backbone . . . etc.) were deﬁned referring to a
R ∈ PSR(G). We now need counterparts of these concepts without referring to a speciﬁc R. For a
concept x deﬁned previously, we will use virtue x or simply v-x for the counterpart of x. (For example,
v-cut for virtue cut, v-chain for virtue chain, v-backbone for virtue backbone). A v-G-pair (v-M-triple,
respectively) is similar to a G-pair (M-triple, respectively) but without referring to a speciﬁc R ∈
PSR(G). Whenever Algorithm 1 adds a gadget g to G̃ through a G-pair (or a M-triple, respectively),
Algorithm 2 adds g into Ṽ and add a corresponding v-G-pair (or v-M-triple, respectively) into V̂.
Initially, V̂ is empty and Ṽ contains only the initial fan g0 = F(vS , vE , vN ). In each step, the algorithm
ﬁnds either new v-G-pairs (g, g R ) with gR ∈ Ṽ; or new v-M-triples (gB , g, g U ) with gB , g U ∈ Ṽ. In either
case, it adds g into Ṽ. But instead of using a R ∈ PSR(G), Algorithm 2 relies on the information stored
in Ṽ and V̂ to ﬁnd v-G-pairs and v-M-triples.
Fix a step in Algorithm 2 and consider the sets Ṽ and V̂ after this step. Any simple path C in G from
vS to vN is called a v-cut of G. A gadget pair (g, gR ) is called a v-G-pair if gR ∈ Ṽ and β(g) ⊆ α(gR ).

14

For a v-cut C, deﬁne:
Ṽ(C) = {g ∈ Ṽ | α(g) intersects C}
V̂(C) = {Λ ∈ V̂ | the frontiers of at least two gadgets of Λ intersect C}
Let e1 and et be the ﬁrst and the last edge of C. A subset of gadgets D ⊆ Ṽ(C) is called a v-support
of C if the following conditions hold:
• The gadgets in D can be arranged into a sequence (g1 , g2 , . . . , gk ) such that e1 ∈ α(g1 ), et ∈ α(gk )
and, when walking along C from vS toward vN , we encounter these gadgets in this order.
• Any two (or three) consecutive gadgets (gi , gi+1 ) (or (gi−1 , gi , gi+1 )) belong to a connection in V̂.
If a set S of connections formed by the gadgets in a v-support of C satisﬁes the structure property
described in Deﬁnition 29, S is called a v-chain of C. Clearly, any chain is also a v-chain.
Let g be a mirror fan with L = β(g). Let a and b be the lowest and the highest vertex of L, and el
and eh the ﬁrst and the last edge of L, respectively. Deﬁne:
Ṽ(L) = {g ∈ Ṽ | α(g) intersects L}
V̂(L) = {Λ ∈ V̂ | the frontiers of at least two gadgets of Λ intersect L}
A subset of gadgets D ⊆ Ṽ(L) is called a v-support of L if the following conditions hold:
• The gadgets in D can be arranged into a sequence (g B = gp , g2 , . . . , gq = g U ) such that el ∈ α(gB ),
eh ∈ α(gU ) and, when walking along L from a toward b, we encounter these gadgets in this order.
• Any two (or three) consecutive gadgets (gi , gi+1 ) (or (gi−1 , gi , gi+1 )) belong to a connection in V̂.
If a set S of connections formed by the gadgets in a v-support of L only satisﬁes the order property
L and the third property described in Deﬁnition 32, S is called a v-backbone of L. If there is a vbackbone(L), we call (g B , g, g O ) a v-M-triple. Both v-G-pairs and v-M-triples are called v-connections.
First, we bound the number of loop iterations in Algorithm 2. By Lemma 13, the number of gadgets
in G is at most N = O(n2 ). So the number of v-G-pairs is at most O(N 2 ) and the number of v-M-triples
is at most O(N 3 ). Hence V̂ contains at most O(n6 ) elements. Since each iteration adds at least either
a v-G-pair or a v-M-triple into V̂, the number of iterations is bounded by O(n6 ).
We need to describe how to perform the operations in the loop body, which is clearly dominated by
ﬁnding v-G-pairs and ﬁnding v-M-triples. Given two gadgets g, gR and the sets Ṽ and V̂, it is easy
to check if (g, g R ) is a v-G-pair (i.e. gR ∈ Ṽ and β(g) ⊆ α(gR )) in polynomial time. However, ﬁnding
v-M-triples (gB , g, g U ) is much more diﬃcult. In §5.2, we show this can be done, in polynomial time, by
ﬁnding a v-backbone(β(g)) consisting of connections in V̂. This will establish the polynomial run time
of the repeat loop of Algorithm 2.
Lemma 34. Let S be the set of all v-backbones of gT . (Because L = β(gT ) is a v-cut, each v-backbone
of L is actually a v-chain of G.) For each R ∈ PSR(G) with its associated cut C = C(R), there exists
a v-chain S ∈ S (which is a v-backbone of L) generated by Algorithm 1 such that S = chain(C).
Proof: For each mirror fan g with L = β(g), if g is in some partial slant REL, then its backbone follows
the order L . So we have G̃ ⊆ Ṽ and {Con(R)|R ∈ PSR(G)} ⊆ V̂. Since we use the two supersets Ṽ
and V̂ of G̃ and Ĝ to ﬁnd v-backbones of gT (chains of G), we immediately have:
{chain(C)|R is a slant REL of G with its associated cut C = C(R)} ⊆ S.

15

In this subsection, we have described Algorithm 2 which constructs (1) the set S of v-chains such
that chain(C) of each partial REL R ∈ PSR(G) with its associated cut C = C(R) is included in S,
(2) the set V̂ of v-connections containing each connection Λ ∈ {Con(R)|R ∈ PSR(G)}, (3) the set Ṽ of
gadgets containing each gadget g ∈ G̃.
Lemma 34 states that any chain is a v-chain. But the reverse is not necessarily true. In §5.3, we
provide an example that a v-chain is not equal to the chain of the associated cut of any partial slant
REL. Thus we need to check whether a v-chain constructed by Algorithm 2 is really a chain of a slant
REL R of G. In §5.4, we describe a backtracking algorithm to detect all such v-chains.

5.2

Algorithm for Finding v-Backbones and v-M-triples

Consider a gadgets (g B , g O , gU ) with the back boundary L = β(gO ). Let a and b be the lowest and the
highest vertex of L, e1 and e2 the ﬁrst and the last edge of L. In this subsection, we show how to check
whether (gB , g O , gU ) is a v-M-triple or not in polynomial time. By the deﬁnition of v-M-triples, this is
equivalent to ﬁnding v-backbone(L)s by using the v-connections in V̂.
Let Ṽ(L) be the set of gadgets in Ṽ that can be in any v-backbone(L). From the conditions described
in Deﬁnition 32, Ṽ(L) contains the gadgets g ∈ Ṽ that satisfy the following conditions:
• The front boundary of g intersects L and g belongs to some v-connection Λ ∈ V̂.
• the front boundary of gB contains e1 ; and (g O , gB ) is not a forbidden pair.
• the front boundary of gU contains e2 ; and; and (g O , gU ) is not a forbidden pair.
To determine which gadgets in Ṽ(L) can form a v-backbone of L, we construct a directed acyclic
graph HL = (VL , EL ) as follows:
Definition 35. Given a triple (g B , gO , gU ) with L = β(g O ), the backbone graph HL of gO is defined as
follows:
• VL = {(l, g)|l = L ∩ α(g) and g ∈ Ṽ(L)} and
• EL = {(l1 , g1 ) → (l2 , g2 )|
{g1 , g2 } belongs to a v-connection Λ ∈ V̂(L) and l1 ∪ l2 is contiguous on L }
A source (sink, respectively) vertex has no incoming (outgoing, respectively) edges in HL . The
intuitive meaning of a directed path P ∈ HL=β(gO ) from the source to the sink is that P corresponds
to a v-backbone of L = β(g O ) and for each vertex (l, g) ∈ P , g corresponds a gadget in a v-backbone
and l is equal to the intersection L ∩ α(g) of L and the front boundary of g. Moreover, for diﬀerent vM-triples of gO Λ1 = (gB1 , gO , g U1 ), Λ2 = (gB2 , gO , gU2 ) ∈ V̂(L), we have vertices vO = (L ∩ α(g O ), gO )
′ = (L ∩ α(g O ), g O ) in H to represent g O such that Λ and Λ represent diﬀerent subpaths
and vO
L
1
2
in HL : one is (L ∩ α(gB1 ), g B1 ) → vO = (L ∩ α(gO ), g O ) → (L ∩ α(gU1 ), gU1 ) and the other one is
′ = (L ∩ α(g O ), g O ) → (L ∩ α(g U2 ), g U2 ) where the vertex v represents the mirror
(L ∩ α(gB2 ), gB2 ) → vO
O
′
fan in Λ1 and vO represents the mirror fan in Λ2 .
Lemma 36. HL is acyclic and can be constructed in O(|V̂|2 ) time.
Proof: Consider a g ∈ Ṽ. Knowing L, we can easily determine if g is in Ṽ(L) in constant time. So we
can identify the set VL in O(|V̂|) time. For two vertices (l, g) and (l′ , g′ ) in VL , the edge (l, g) → (l′ , g′ )
exists if and only if the following two conditions are satisﬁed: (1) g and g ′ belong to some v-connection
in V̂(L); (2) l ∪ l′ is contiguous on L; and (2) when walking along L upwards, we encounter the gadgets g
before g′ . These two conditions can be easily checked in constant time. So the set EL can be determined
in O(|VL |2 ) = O(|V̂|2 ) time. Thus HL can be constructed in O(|V̂|2 ) time.
The edge directions of HL are deﬁned by the relation L . Since L is acyclic, HL is acyclic.
16

Lemma 37. Given a triple (gB , gO , g U ) with L = β(gO ), let HL be the graph defined in Definition 35.
1. Each directed path from the source to the sink in HL corresponds to the v-M-triple (gB , gO , gU ).
2. The v-M-triple (gB , gO , gU ) corresponds to a set of directed paths from g B to gU in HL .
Proof: Statement 1. Consider any directed path (lB , gB ) → · · · → (lU , gU ) from the source (lB , gB ) to
the sink (lU , g U ) in HL . Since each directed edge (l, g) → (l′ , g′ ) in HL follows the order L on L, each
directed path from (lB , gB ) to (lU , gU ) is a v-backbone of gO and (g B , gO , g U ) is a v-M-triple.
Statement 2: Consider a v-M-triple (gB , g O , gU ). This means that there exists a v-backbone gB L
g2 L · · · L gk−1 L gU on L. Because each g L g′ on L is a directed edge (l, g) → (l′ , g′ ) in HL , we
have that (lB , g B ) → (l2 , g2 ) → · · · → (lk−1 , gk−1 ) → (lU , gU ) is a directed path from (lB , gB ) to (lU , gU )
in HL .
Note that there may exist multiple paths in HL from (lB , gB ) to (lU , g U ). All these paths correspond
to the same v-M-triple (g B , g O , gU ). The intuitive meaning of this fact is as follows. When we add g O
via the v-M-triple (gB , g O , gU ), even though the gadgets g B and g U are ﬁxed, the v-connections and
gadgets in the v-backbone(L)s between g B and gU may be diﬀerent. But as long as they form a valid
v-backbone(L), we can add g O .
The following Algorithm 3 ﬁnds v-M-triples (gB , gO , gU ) by ﬁnding v-backbone(L)s.
Algorithm 3: Find v-M-triples
3.1
3.2
3.3

Input: A triple (gB , gO , g U ) with L = β(gO ) and the set V̂ of v-connections
From the connections in V̂, identify the set V̂(L);
Construct the directed graph HL as in Deﬁnition 35;
By using Lemma 37, return whether (gB , gO , gU ) is v-M-triple or not;

Theorem 38. Given a gadgets triple (gB , gO , gU ), Algorithm 3 can successfully test whether (gB , g O , gU )
is a v-M-triple in polynomial time.
Proof: The correctness of the algorithm follows from Lemma 37. By Lemma 36, the steps 1 and 2 can
be done in polynomial time.
Step 3: Since HL is acyclic, we can use breadth-ﬁrst search to ﬁnd whether (lU , gU ) is reachable from
B
(l , gB ). Then (gB , g, g U ) is a v-M-triple if and only if (lU , gU ) is reachable from (lB , gB ). This step is
carried out by calling breadth-ﬁrst search which takes polynomial time. So the total time for this step
is polynomial.
Note that the total number of source to sink paths in HL can be exponential. However, we only need
to ﬁnd one path from (lB , gB ) to (lU , gU ).

5.3

An Example that A v-Chain Does Not Have A Slant REL

In this subsection, we present an example to show why a v-chain deﬁned in the last subsection does
not necessarily have a corresponding partial slant REL. Imagine that we have two v-chains C and C ′ .
Suppose that C can be partitioned into C = (C1 , C2 , C3 ) and C ′ can be partitioned into C ′ = (C1′ , C2′ , C3′ )
such that C2 = C2′ , then we may have another two v-chains (C1 , C2 = C2′ , C3′ ) and (C1′ , C2 = C2′ , C3 ).
However, both of the two v-chains can’t correspond any partial slant REL. Fig 39 (3) shows a v-chain
(g1 , g2 , g3 , g4 , g5 , g6 ) which can’t have a corresponding partial slant REL where (g1 , g2 , g3 ) from R1 and
(g3 , g4 , g5 , g6 ) from R2 shares a common gadget g3 .

17

g3
g2
g1

1

g4

g3

gA
g0

(1)

2

g5

gF

gE gD g

g6

g4

g3

R

g2

g5 g6

g1

C

gB

g0

(2)

(3)

Figure 39: (1) is a partial slant REL R1 which consists of gadgets {g0 , gA , gF , g1 , g2 , g3 }; (2) is a partial
slant REL R2 which consists of gadgets {g0 , g3 , g4 , g5 , g6 , gB , gC , gD , gE }; (3) (g1 , g2 , g3 , g4 , g5 , g6 ) is a
v-chain where (g1 , g2 , g3 ) is a subchain of R1 and (g3 , g4 , g5 , g6 ) is a subchain of R2 . However, the v-chain
is not coming from the same partial slant REL. {g1 , g2 , g3 } can be added into R1 only when {g0 , gA }
have been added into R1 . The order of added gadgets in R2 is: (g0 , gB , g6 , g5 , gC , gD , gE , g3 , g4 ). But,
gA and each gadget of {gB , gC , gD , gE } can not coexist in the same REL because some faces of gA and
each gadget of {gB , gC , gD , gE } overlap.

5.4

An Algorithm to Find Conflicting Gadgets via Backtracking

In the last subsection, we know that each v-chain of gT only contains partial information of a complete
slant RELR. In this subsection, we use a recursive constructive deﬁnition to deﬁne a hierarchal v-chain
which represents suﬃcient information of a complete REL R and can be represented by a DAG as
follows:
Definition 40. Given the final mirror fan gT with C = β(gT ), a hierarchal v-chain J = (V (J ), E(J ))
of C is a DAG recursively defined as follows:
1. The root J (r) ∈ V (J ) is a sequence of pairs ((C1 , g1 ), (C2 , g2 ), · · · , (Ck , gk )) where
(a) (g1 , g2 , · · · , gk ) is a v-chain (g1 C g2 C · · · C gk ) of C and
(b) each Ci = C ∩ α(gi ), 1 ≤ i ≤ k, is a portion of the front boundary α(gi ) of gi .
2. While(α(g0 ) * C)
(a) select a gadget g such that
i. α(g) ⊆ C and
ii. there exist a sequence of pairs ((l1 , g) ∈ S1 , (l2 , g) ∈ S2 , · · · , (lh , g) ∈ Sh ) where each
Si , 1 ≤ i ≤ h, is a vertex of J and l1 ∪ l2 ∪ · · · ∪ lh = α(g),
(b) create a vertex S consisting of a sequence of pairs ((l1 , g1 ), (l2 , g2 ), · · · , (lh , gh )) where
i. (g1 L g2 L · · · L gh ) is a v-backbone of L = β(g) and
ii. each li = L ∩ α(gi ), 1 ≤ i ≤ h, is a portion of the front boundary α(g) of g,
(c) add S into V (J ) and for each Si , 1 ≤ i ≤ h, add an arc Si → S into E(J ). And,
(d) change C to C(vS , a) ∪ β(g) ∪ C(b, vN ) where a and b are the first and the last vertices of
β(g), respectively.
Intuitively a hierarchal v-chain J is a hierarchal decomposition of a complete slant REL R and
the root J (r) of J represents a chain(C) of R’s associated cut C = C(R). In the following deﬁnition,
a hierarchial structure H consists of a set of DAGs (backbone graphs) and H can implicitly store all
possible hierarchal v-chains J .
18

Definition 41. H = (V (H), E(H)) is a DAG where
1. for each vertex v ∈ V (H), v represents a DAG H(v) = (V (H(v)), E(H(v))) over V (H(v)) where
(a) every vertex w ∈ V (H(v)) is a pair (l, g) and l is a portion of the front boundary α(g) of g,
(b) for each arc e = (ue → u′e ) in E(H(v)), e associates with a DAG H(v ′ ), v ′ ∈ V (H) (the
associated DAG of e is denoted by H(e)), the source of H(e) is the starting vertex ue of e and
the sink of H(e) is the ending vertex u′e of e.
2. an ordered pair (u, v) belongs to E(H) if there exists an arc e in E(H(u)) such that e’s associated
DAG H(e) is equal to H(v).
We call an ordered pair vertices (u, v) ∈ E(H) a super arc of H. Also, for each arc e ∈ E(H(u)), let He
be the maximal subgraph of H which can be reached from H(e) via super arcs.
From now on, (1) when we mention a DAG H(e) from an arc, it means that the arc e is in the DAG
represented by a vertex in V (H), (2) when we mention a DAG H(v) represented by a vertex v, it means
that the vertex v is a vertex in V (H), and (3) we use the term H(eC ) to represent the DAG in the root
of the hierarchal structure H.
Given a fan g and an arc e = (l1 , g1 ) → (l2 , g2 ) ∈ E(H(v)), (1) e is a complete arc on g if g = g1 = g2 ,
(2) e is a left partial arc on g if g 6= g1 and g = g2 , (3) e is a right partial arc on g if g = g1 and g 6= g2 ,
and (4) e is minimal if l1 ∪ l2 is a contiguous path. Algorithm 4 emulates the growing process of all
hierarchal v-chains J as follows:
1. add the root v into H and let H(r) be the backbone graph HC=β(gT ) of gT . Now, V (H) = {r} and
the root J (r) of each hierarchal v-chain J is a directed path P ∈ H(v), and vice versa.
2. iteratively selects a gadget g (to be deﬁned in Deﬁnition 44) such that
if g is a mirror fan and has a path P = (· · · , (lB , g B ), (l = α(g), g), (lU , gU ), · · · ) ∈ H(v), (1) add
a vertex v ′ into V (H), (2) let H(v ′ ) be the backbone graph HL′ =β(g) of g, (3) change P to
(· · · , (lB , gB ), (lU , gU ), · · · ) ∈ H(v), (4) add a super arc from v to v ′ in E(H) and (5) let H(e′ )
be H(v ′ ) where e′ = (lB , gB ) → (lU , gU ). The backbone graph of g is embedded into H(e′ ).
See Fig 42 as an example.
Otherwise, g is a fan. For each maximal path P = (v1 , v2 , · · · , vk ) ∈ H(v), v ∈ V (H) where the
gadget gi of each vi = (li , gi ) is equal to g, (1) merge P , (2) add an arc e′ between v1 and vk
and (3) set H(e′ ) = (β(g) ∩ α(g R ), g R ) (the backbone graph of g) where (g, g R ) is a v-G-pair
in V̂. The backbone graph of g is embedded into H(e′ ). Figs 43 (1) and (2) show an example
of P before merging P and Figs 43 (3) and (4) show an example of P after merging P .
The next deﬁnition deﬁnes a removable gadget g which can be selected in Algorithm 4 and add the
backbone graph HL=β(g) into H . Intuitively a removable gadget g means that all gadgets g ′ which are
connections (g′ , g) in V̂ have been selected and removed from Algorithm 4.
Definition 44. In Algorithm 4, we say a gadget g is removable from a DAG H(e) V (H) if there exists
a vertex (l, g) ∈ H(e) and we cannot find a vertex (l′ , g′ ) from another DAG H(e′ ) in V (H) such that g
and g′ belong to some connection Λ ∈ V̂. Note that the vertex (l′ , g′ ) can also be selected from H(e).
Now we give the deﬁnition of a conflicting hierarchal v-chain J which cannot form a slant REL R.
An example for a conflicting hierarchal v-chain J has been shown in Fig 39.
Definition 45. A hierarchal v-chain J is conﬂicting on a gadget g if there exist pairs (l, g) ∈ S and
(l′ , g′ ) ∈ S ′ where S and S ′ are two vertices in V (J ) such that
19

e2

e3

e1

e4

g
g1

g3

g2

v1

e1
gB

gU

gB

(2)



e1
1 2

g1



3



4





5

e4

v1

e1
g

6

e4

!


g2 g3

g

v5

gU

g

(1)



e4

e3

e2

5

,-

6

"#

1

g

g

$%

2

g1

(3)

()

&'

3

g2

4

*+

5



g

g

g3

(4)

Figure 42: (1) and (2) show a M-triple (gB , g, g U ) and suppose that HC has a directed path P = (· · · ,
e1 , e2 , e3 , e4 , · · · ); (3) and (4) show that after removing g, we add a new arc e′ into HeC and P becomes
(· · · , e1 , e′ , e4 , · · · ) ∈ HC . And, (e′1 , e′2 , e′3 , e′4 , e′5 , e′6 ) is a directed path in H(e′ ) where (e′1 , e′2 , e′3 , e′4 ,
e′5 , e′6 ) is a v-backbone of L = β(g).
1. if g 6= g′ , g and g′ overlap at least one face.
2. Otherwise (g = g′ ), l and l′ overlap at least two vertices.
Note that S might be equal to S ′ . Moreover, we say the vertex (l′ , g′ ) is conﬂicting to (l, g) on g if (l, g)
and (l′ , g ′ ) satisfy one of the above two conditions. On the other hand, we say (l′ , g′ ) is compatible
to (l, g) on g if (l′ , g′ ) is not conflicting to (l, g) on g. And, for a hierarchal v-chain J , we say J is
compatible on g if J is not conflicting on g.
Next we can start to deﬁne that H is compatible on a gadget g as follows:
Definition 46. Given a hierarchal structure H = (V (H), E(H)) and a gadget g ∈ Ṽ, we say H is
compatible on g if
1. there exists a directed path P ∈ H(eC ) such that for each vertex (l, g) ∈ P , each vertex (l′ , g ′ ) ∈ P
other than (l, g) is compatible to (l, g) on g. And,
2. for each arc e ∈ P , the hierarchal substructure He of H is also compatible on g.
We say (1) a directed path P ∈ H(eC ) is compatible on g if P satisfies the conditions 1 and 2. And, (2)
a directed path P ∈ H(eC ) is conﬂicting on g if P violates the condition 1 or the condition 2. Moreover,
an arc e ∈ P is compatible on g if He is compatible on g. On the other hand, e is conﬂicting on g if
He is not compatible on g.
From the above deﬁnition of a compatible hierarchal structure H, we immediately have a recursive
procedure to check whether there exists a compatible path P on g in H(eC ) as follows: for each directed
path P ∈ H(eC ), recursively check each arc e ∈ P whether the DAG H(e) ∈ He (H(e) is the root’s
associated DAG in He ) has a compatible directed path on g or not. Then P is conﬂicting on g if and
only if P becomes disconnected after removing all conﬂicting arcs e on g from H(eC ). It is stated in
Property 54.

20

e2
e1

e1
e41 5

1

e11

e12

e21 e3

e22

e13
g

e14

e4

e1
1 2

e1

e24

gR

(1)
e1

e3
e23

JK

gI

e2
2
2
e11
e51 e1 e2
1
1
1
e
1 e 2
/1
52
1 2 1 e3 4 4
1
1
0
1
2
3
1

e34

62

83

e3

e4

94

:5

e14 e4 e4
2 3

e13 e23
L3

44

34

1

2

1

(2)

e4
e24

e 31

e1

e4 .

e34

=1

e1

e11

1
e21 e3
1
?
1
@

g

(3)

;<

>2
PQ

1

H4
MN

2

gC

(4)

e4
e24 e4
3

G5

gE

Figure 43: (1) and (2) are an example of H, complete arcs and partial arcs; (3) and (4) are an example
to explain how H changes its structure after removing a fan g; (1) and (2): (· · · , e1 , e2 , e3 , e4 , · · · ) is a
directed path P ∈ H(eC ) where e1 is a left partial arc on (g, gR ), {e2 , e3 } are complete arcs on (g, gR ) and
e4 is a right partial arc on (g, gR ). Also, (e11 , e12 , e13 , e14 , e15 ) is a directed path in H(e1 ), (e21 , e22 ) is a directed
path in H(e2 ), (e31 , e32 ) is a directed path in H(e3 ) and (e41 , e42 , e43 ) is a directed path in H(e4 ); (3) and
(4): after removing the fan g, change the vertices v2 = (l2 , g) and v4 = (l4 , g) to v2 = (β(g) ∩ α(gR ), gR )
and v4 = (β(g) ∩ α(gR ), gR ), respectively where β(g) ∩ α(gR ) is the intersection of the back boundary
β(g) and the front boundary α(gR ), and (g, g R ) is a G-pair in Ṽ. Also, the arcs {e2 , e3 } are replaced by
the arc e′ and H(e′ ) is the path (v2 , (β(g) ∩ α(gR ), g R ), v4 ).
Brieﬂy speaking, Algorithm 4 iteratively removes the root J (r) of a conﬂicting hierarchal-v-chain J
from H(eC ). Also, we utilize Algorithms 5 and 6 to adjust the structure of H. Moreover, after recursively
adjusting H (it means that via adjusting H(eC ) ∈ H, we also adjust the structure of He , e ∈ H(eC )),
we have the following fact: for each H(e) ∈ H, if there does not exist a directed path between v1 and
v2 in H(e) before removing g from H(e), then v1 remains disconnected to v2 in H(e) after removing g
from H(e). At the end of Algorithm 4, we can conclude that each connected path P ∈ H(eC ) has a
corresponding compatible hierarchal v-chain J . The intuitive meaning of a path P ∈ H(eC ) keeps its
connectivity after removing g is that P can add g into its corresponding hierarchal v-chain J .
How to eﬃciently check whether a directed path P ∈ H(eC ) is compatible on g or not? We can
recursively check whether there exists a compatible directed path P ′ ∈ H(e) on g for each complete and
partial arcs e ∈ H(eC ). In Observations 48 and 51, we describe the recursive formulas to check complete
arcs and partial arcs whether they are compatible on g or not. After we check all complete arcs and
partial arcs, we keep all compatible arcs on g in H(eC ) and check whether there exists a directed path
from source to sink in H(eC ). (The root J (r) of a compatible hierarchal v-chain J .) The recursive
procedures to check directed paths, complete arcs and partial arcs on g in H(eC ) are described in Lemmas
47, 50 and 53, respectively.
The main task for EXPAND operation in Algorithm 5 is to add the backbone graph of a mirror fan
into H. See Fig 42 as an example for EXPAND operation.
In the following lemma, we describe the recursive structure of a compatible directed path P ∈ H(eC ).
A simple way to explain Lemma 47 is that to recursively check a compatible directed path P in H(eC )
is equal to, for each arc e ∈ P , recursively check whether there exists a compatible directed path P ′ in
H(e). In general, each directed path P ∈ H(eC ) can be decomposed into ﬁve parts: (1) the subpath
from source which doesn’t have any partial arc and complete arc on g, (2) the subpath which only has
a left partial arc on g, (3) the subpath which only has complete arcs on g, (4) the subpath which only
has a right partial arc on g and (5) the subpath to sink which doesn’t have any partial arc and complete
arc on g. Because each arc e in a compatible directed path P must be compatible on g , it implies that
21

Algorithm 4: Find Conﬂicting Gadgets via Backtracking Algorithm
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
4.10

4.11
4.12
4.13
4.14
4.15
4.16

4.17
4.18
4.19
4.20

Input: Sets Ṽ and V̂
Add the backbone graph HC=β(gT ) of gT into H. V (H) = {H(eC ) = HC };
while the initial fan g0 is not removable from H(eC ) do
Find a removable gadget g from H(eC );
if g is a mirror fan then
for each M-triple (g B , g, gU ) ∈ V̂ do
EXPAND g in H by Algorithm 5;
end
else if g is a fan then
for each G-pair (g, g R ) do
Recursively check whether each complete arc and partial arc in H(eC ) are compatible
on g or not by Algorithm 6;
end
Recursively delete all complete arcs on g from H(eC );
end
Remove g from Ṽ and all connections (g, gR ) and (gB , g, gU ) from V̂;
end
if there exists a path P = (e1 , e2 , · · · , ek ) ∈ H(eC ) where each ei , 1 ≤ i ≤ k, is a complete arc on
g0 then
G have an area-universal rectangular layout;
else
G does not have any area-universal rectangular layout;
end

H(e) must have at least one directed path from source to sink which is compatible on g. We describe
their recursive structures of complete arcs and partial arcs on g in Observations 48, 49, 51 and 52. From
the above discussion, we immediately have Lemma 47.
Lemma 47. Given a fan g, suppose there is a directed path P = (e1 , e2 , ez , ep , ec1 , ec2 , · · · , eckc , eq ,
e′1 , e′2 , · · · , e′z ′ ) ∈ H(eC ) where the arcs ep and eq are the left and right partial arcs on g, respectively,
and each arc eci , 1 ≤ i ≤ kc , is a complete arc on g. Then, P is the root J (r) of a compatible hierarchal
v-chain J on g if and and if
• for each complete arc eci ∈ P, 1 ≤ i ≤ kc , there is a compatible directed path Pic ∈ H(eci ) on g (see
Observations 48 and 49 for more details of a complete arc),
• for the left partial arc ep ∈ P , there is a compatible directed path P p ∈ H(ep ) on g (see Observations
51 and 52 for more details of a left partial arc) and
• for the right partial arc eq ∈ P , there is a compatible directed path P q ∈ H(eq ) on g (see Observations 51 and 52 for similar details of a right partial arc).
Given a complete arc e = (l1 , g) → (l2 , g) ∈ H(eC ) on g, each arc e′ ∈ P is also a complete arc on
g. And, we know that if we want to guarantee that a complete arc e is compatible, we must recursively
check whether H(e) can have a directed path which only consists of compatible complete arcs on g.
Obviously, to recursively check a compatible complete arc on g is a recursive procedure implemented by
dynamic programming technique. Also, the base case for the recursive procedure is that a complete arc
on g whose two end vertices (l1 , g) and (l2 , g) have that l1 ∪ l2 is contiguous on the front boundary of g.
It means that (l1 , g) → (l2 , g) is compatible on g. See Fig 43 as an example of a complete arc.
22

Algorithm 5: EXPAND a mirror fan in H
5.1
5.2

5.3
5.4
5.5

5.6
5.7

Input: The hierarchal structure H with the root H(eC ) and a M-triple (gB , g, gU ) ∈ V̂
Add the backbone graph HL=β(g) into H as a vertex v ∈ V (H);
e1
e2
for each DAG H(e) ∈ V (H) such that there is a subpath (l1 , gB ) −→
(α(g), g) −→
(l2 , g U ) in H(e)
where l1 and l2 are portions of α(gB ) and α(gU ), respectively do
e

e′

e

1
2
Replace (l1 , gB ) −→
(α(g), g) −→
(l2 , gU ) by (l1 , gB ) −
→ (l2 , gU ) in H(e);
Set H(e′ ) = H(v) and add a super arc from H(e) to H(v) in H;
Add an arc from the starting vertex of e to the source vertex of H(v) and an arc from the sink
vertex of H(v) to the ending vertex of e in H(e);
Remove the vertex (α(g), g) from H(e);
end

From the above discussion, we can describe recursive structures of a compatible complete arc on g
in Observations 48 and 49:
Observation 48. Given a fan g, a complete arc e is compatible on g if and only if there exists a directed
path P = (ec1 , ec2 , · · · , eckc ) ∈ H(e) where
• the source vertex of P is the starting vertex of e,
• the sink vertex of P is the ending vertex of e and
• each eci , 1 ≤ i ≤ kc , is a compatible complete arc on g.
Observation 49. Given a fan g, a minimal complete arc e = (l1 , g) → (l2 , g) is compatible on g if and
only if l1 ∪ l2 is contiguous on the front boundary α(g) of g (the last vertex of l1 overlaps the first vertex
of l2 ).
Based on Observations 48 and 49, we can check a complete arc e ∈ H(eC ) on g whether it is
compatible on g or not via Lemma 50.
Lemma 50. Given a fan g, we can recursively check whether each complete arc e ∈ H(eC ) on g satisfies
structure described in Observations 48 and 49 as follows:
1. recursively check whether each arc e′ ∈ H(e) satisfies the structures in Observations 48 and 49,
2. keep all arcs passing the above tests in H(e), and
3. check whether H(e) has a directed path from source to sink. If yes, keep e in H(eC ). Otherwise,
delete e from H(eC ).
For a left partial arc e = (l1 , g1 ) → (l2 , g2 ) ∈ H(eC ) on g, because g2 is equal to g, each directed
path P in H(e) can be partitioned into (1) the subpath that consists of neither complete arcs nor partial
arcs on g, (2) the left partial arc on g and (3) the subpath that only consists of complete arcs on g.
See Fig 43 as an example of a left partial arc. Similarly, to check a compatible left partial arc on g is
a recursive procedure which can be implemented by dynamic programming technique. Also, the base
case for the recursive procedure is a left partial arc (l1 , g1 ) → (l2 , g2 = g) on g which has (1) (g2 = g, g1 )
is a v-connection in V̂ and (2) l1 ∪ l2 is contiguous on the front boundary α(g2 , g1 ) of the connection
(g2 , g1 ). It means that (l1 , g1 ) → (l2 , g2 = g) is compatible on g. See Fig 43 for examples of a left partial
arc and a minimal left partial arc. From the above discussion, we can describe recursive structures of a
compatible left partial arc on g in Observations 51 and 52:
23

Observation 51. Given a fan g and a left partial arc e on g, a left partial arc e is compatible on g if
and only if there exists a directed path P = (e1 , e2 , · · · , ez , ep , ec1 , ec2 , · · · , eckc ) in H(e) where
• the source vertex of P is the starting vertex of e,
• the sink vertex of P is the ending vertex of e,
• for each 1 ≤ i ≤ z, ei = (li , gi ) → (li+1 , gi+1 ) is an arc where g 6= gi and g 6= gi+1 ,
• the arc ep is a compatible left partial arc on g, and
• each arc eci , 1 ≤ i ≤ kc , is a compatible complete arc on g.
Observation 52. Given a fan g, a minimal left partial arc e = (l1 , g1 ) → (l2 , g2 = g) on g is a compatible
left partial arc on g if and only if (1) (g2 = g, g1 ) is a connection in V̂ and (2) l1 ∪ l2 is contiguous on
the front boundary α(g2 , g1 ) of the connection (g2 , g1 ) (the last vertex of l1 overlaps the first vertex of
l2 ).
Based on Observations 51 and 52, we can recursively check whether a partial arc e ∈ H(eC ) is
compatible on g or not via Lemma 53.
Lemma 53. Given a fan g, we can recursively check whether a partial arc e ∈ H(eC ) on g satisfies the
structures in Observations 51 and 52 as follows:
1. recursively check whether each partial arc e′ ∈ H(e) on g satisfies the structures in Observations
51 and 52,
2. recursively check whether each complete arc e′ ∈ H(e) on g satisfies the structures in Observations
48 and 49,
3. keep all arcs passing the above tests in H(e), and
4. check whether H(e) has a directed path from source to sink. If yes, keep e in H(eC ). Otherwise,
delete e from H(eC ).
There are three main tasks of MERGE operation in Algorithm 6. The ﬁrst one is to recursively check
each complete arc on a removable gadget g ∈ Ṽ. The second one is to recursively check each partial arc
on g. The ﬁnal one is to remove g and maintain the connectivity for each compatible directed path in
H(eC ). What we do in the ﬁnal for loop is to reconnect a new arc between a left partial arc eL and a
right partial arc eR if and only if there exists a compatible directed path from eL to eR . See Fig 43 as
an examples for Algorithm 6.
Note that the connectivity between vL and vR is based on the arcs which are compatible on g in
Algorithm 6.
There are two important properties for the correctness of Algorithm 4. The ﬁrst one states that
we can eliminate each conﬂicting directed path P (hierarchal v-chain J ) on g via removing g from
H(eC ). The second one states that the number of directed paths (hierarchal v-chains) decreases during
Algorithm 4 executes.
Property 54. For each DAG H(e) ∈ V (H), a directed path P ∈ H(e) is conflicting on g if and only if
P becomes disconnected after removing g from H(e).
Property 55. For each DAG H(e) ∈ V (H), if any two vertices u, v ∈ H(e) are disconnected, then u
and v remain disconnected after removing g from H(e).

24

Algorithm 6: MERGE H via Dynamic Programming
6.1
6.2

6.3
6.4
6.5

6.6
6.7

6.8

6.9

6.10

Input: The hierarchal structure H with the root H(eC ) and a G-pair (g, gR ) ∈ V̂
for each complete arc ec ∈ H(eC ) on g do
Recursively check ec whether ec is compatible on g or not (this recursive check follows Lemma
50);
end
for each partial arc ep ∈ H(eC ) on g do
Recursively check ep whether ep is compatible on g or not (this recursive check follows Lemma
53);
end
for each pair of left partial arc eL = va → vL = (vL , g) and right partial arc
eR = vR = (vR , g) → vb in H(eC ) such that vL and vR remain connected in H(eC ) do
Change vL = (vL , g) and vR = (lR , g) to vL = (β(g) ∩ α(g R ), gR ) and vR = (β(g) ∩ α(g R ), gR ),
respectively;
Add an arc e′ = (vL → vR ) into the graph H(eC ) and let H(e′ ) be the directed path
(vL → (β(g) ∩ α(g R ), gR ) → vR );
end

From the above two properties, we can see that if we can recursively guaranteed that for each
compatible arc e ∈ H(eC ) on g, H(e) has Properties 54 and 55, then each compatible directed path
P ∈ H(eC ) on g is also a compatible hierarchal v-chain on g. And, in the ﬁnal "for" loop of Algorithm
6, it connects a new arc between vL and vR if and only if there is a compatible directed path on g from
vL and vR . Hence it guarantees that no pair of vertices (vL , vR ) turns into connected if vL and vR are
disconnected before removing conﬂicting arcs on g.
Theorem 56. Algorithm 4 can successfully check whether there exists a directed path P ∈ H(eC ) such
that P has a corresponding slant REL.
Proof: The correctness of Algorithm 4 is based on Properties 54 and 55. Clearly, from Property 54,
each conﬂicting directed path P ∈ H(eC ) (the root J (r) of each hierarchal v-chain J ) on g becomes
disconnected after removing a removable gadget g and from Property 55, it remains disconnected in
the following steps. Hence in the ﬁnal step of Algorithm 4, each connected directed path P ∈ H(eC )
has been proven that P corresponds to the root J (r) of a compatible hierarchal v-chain on g for every
gadget g ∈ Ṽ. Also, if a directed path P ∈ H(eC ), corresponds to the root J (r) of a hierarchal v-chain
J , keeps its connectivity after recursively removing a gadget g from H(eC ), then this hierarchal v-chain
J can add the gadget g into its corresponding slant REL. Hence we can have that each connected
directed path in H(eC ) has a corresponding slant REL R.
Theorem 56 has proven that we can backtrack all directed paths P ∈ H(eC ) to know whether P
represents the chain of a partial slant REL R.
Theorem 57. The time complexity of Algorithm 4 is polynomial bound.
Proof: Let K be the number of iterations in Algorithm 4 and Ni , 1 ≤ i ≤ K, be the size of H in the
i-th iteration. The time analysis of backtracking is based on three parts: (1) K is polynomial bound,
(2) each Ni , 1 ≤ i ≤ K, is polynomial bound and (3) time complexity T (Ni ) in each i-th iteration is
polynomial bound.
Obviously, the number K of total iterations is bounded by the number of connections V̂. By Lemma
13, the number of gadgets in G is at most N = O(n2 ) and the number of connections in G is at most
O(N 3 ) = O(n6 ). Hence K polynomially grows with respect to the number of G’s vertices n.
25

For each i-th iteration, we either execute EXPAND or MERGE operations to adjust H’ structure.
When Algorithm 4 executes EXPAND operation on a removable gadget g with the back boundary
L = β(g), we add g’s backbone graph HL into H where HL ’s size (the number of vertices in HL ) is
polynomial bound. Since the number K of total iterations is polynomial bound, the total vertices added
into H in all EXPAND operations are bounded by the summation of all backbone graphs’s size. Hence,
the summation of all backbone graphs’s size is polynomial bound.
When Algorithm 4 executes MERGE operation on a removable gadget g with a G-pair (g, gR ), we
replace each maximal compatible directed path P on g in H by an arc e′ = (gu , lu ) → (gv , lv ) between
the two end vertices of P where each arc in P is a complete arc on g, and add H(e′ ) into H where
|H(e′ )| consists of the newly-added vertex (gR , l). Note that the added vertex (gR , l) only connects to
the two end vertices (gu , lu ) and (gv , lv ) of e, and cannot be connected to other vertices in H in following
iterations. Also, (g R , l) is removed from H when removing a removable gadget gR from H. Hence the
total number of newly-added arcs e′ are summation of all backbone graphs’s size and it is polynomial
bound. Also, the size of all added H(e′ ) is polynomial bound.
Because the total vertices added into H are polynomial bound during each iteration and the number
K of iterations is polynomial bound, the maximum of H’s size is polynomial bound of each iteration in
Algorithm 4. Hence each number Ni , i ≥ 1, of vertices of H in each i-th iteration is polynomial bound.
Now we analyze the time complexity of each iteration. When Algorithm 4 executes EXPAND
operation on a removable gadget g with the back boundary L = β(g), we take polynomial time to
add the g’s backbone graph HL into H because HL ’s size is polynomial bound.
When Algorithm 4 executes MERGE operation on a removable gadget g, the tasks of MERGE
operation consist of (1) recursively checking each complete arc on g in H by Lemma 50, (2) recursively
checking each partial arc on g in H by Lemma 53 and (3) check that for each DAG H(e), whether there
exists a directed path from the source to the sink in H(e) after removing all conﬂicting complete and
partial arcs from H(e).
The total work of a MERGE operation can be simply described as follows: check each DAG H(e) ∈
V (H) whether H(e) has at least one connected directed path from the source to the sink in H(e). And,
it can be done by executing a breadth-ﬁrst search in H(e) since H(e) is a DAG. Hence the complexity
of the total work of a MERGE operation is polynomial bound as poly(max1≤i≤K Ni ). Note that the
order to check each DAG H(e) ∈ V (H) is a bottom-up traversal in H as follows: a DAG H(e) ∈ V (H)
is ready to check if and only if every DAG H(e′ ), e′ ∈ E(H(e)), has been checked.
Because each iteration takes polynomial time as T (Ni ) ≤ poly(max1≤i≤K Ni ), the total time complexity of all K iterations in Algorithm 4 is also polynomial bound.
Theorem 57 has proven that the time complexity of Algorithm 4 is polynomial bound.

26

References
[1] M. Bruls, K. Huizing, and J. J. van Wijk, Squariﬁed treemaps, in Proceedings of the Eurographics
and IEEE TCVG Symposium on Visualization, Springer, 2000, pp. 33-42.
[2] C. F. Earl and L. J. March, Architectural applications of graph theory, Applications of Graph
Theory, R. Wilson and L. Beineke, eds., Academic Press, London, 1979, pp. 327-355.
[3] Erik D. Demaine and Martin L. Demaine; Jigsaw Puzzles, Edge Matching, and Polyomino Packing:
Connections and Complexity, Graphs and Combinatorics, 23 [Supple], 2007, Digital Object Identiﬁer
(DOI) 10.1007/s00373-007-0713-4.
[4] D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek, Area-universal and constrained rectangular layouts, SIAM J. Comput. 41, no. 3, 2012, pp. 537-564.
[5] D. Eppstein, Regular labelings and geometric structures, in Proceedings of the 22nd Canadian
Conference on Computational Geometry, 2010, pp. 125-130.
[6] D. Eppstein and E. Mumford, Steinitz theorems for orthogonal polyhedra, in Proceedings of the
26th ACM Symposium on Computational Geometry, 2010, pp. 429-438.
[7] É. Fusy Transversal structures on triangulations, with application to straight-line drawing, in Proceedings of the 13th International Symposium on Graph Drawing (GD 2005), Lecture Notes in
Comput. Sci. 3843, Springer, Berlin, 2006, pp. 177-188.
[8] É. Fusy, Transversal structures on triangulations: A combinatorial study and straight-line drawings,
Discrete Math. 309, 2009, pp. 1870-1894.
[9] X. He, On ﬁnding the rectangular duals of planar triangular graphs, SIAM J. Comput. 22, no. 6,
1993, 1218-1226.
[10] G. Kant and X. He, Regular edge labeling of 4-connected plane graphs and its applications in graph
drawing problems, Theoret. Comput. Sci. 172, (1997), pp. 175-193.
[11] M. van Kreveld and B. Speckmann, On rectangular cartograms, Computational Geometry 37, 2007,
175-187.
[12] K. Koźmiński and E. Kinnen Rectangular duals of planar graphs, Networks 5, 1985, pp. 145-157.
[13] E. Mumford, Drawing graphs for cartographic applications, Ph.D. thesis, Technische Universiteit
Eindhoven, Eindhoven, The Netherlands, 2008.
[14] E. Raisz, The rectangular statistical cartogram, Geographical Review 24 (2), 1934, 292-296.
[15] I. Rinsma, Nonexistence of a certain rectangular ﬂoorplan with speciﬁed areas and adjacency,
Environ. Plann. B 14, 1987, pp. 163-166.
[16] S. Wimer, I. Koren, and I. Cederbaum, Floorplans, planar graphs, and layouts, IEEE Trans.
Circuits Syst. 35, 1988, pp. 267-278.
[17] G. K. H. Yeap and M. Sarrafzadeh, Sliceable ﬂoorplanning by graph dualization, SIAM J. Disc.
Math. 8, 1995, pp. 258-280.

27

