Extending Partial Representations of Rectangular Duals with Given Contact Orientations

Abstract

A rectangular dual of a graph G is a contact representation of G by axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the union of all rectangles is a rectangle. The partial representation extension problem for rectangular duals asks whether a given partial rectangular dual can be extended to a rectangular dual, that is, whether there exists a rectangular dual where some vertices are represented by prescribed rectangles. Combinatorially, a rectangular dual can be described by a regular edge labeling (REL), which determines the orientations of the rectangle contacts. We characterize the RELs that admit an extension, which leads to a linear-time testing algorithm. In the affirmative, we can construct an extension in linear time.

Partially supported by DFG grants Ru 1903/3-1 and Wo 758/11-1.

1 Introduction

A geometric intersection representation of a graph G is a mapping $\mathcal {R}$ that assigns to each vertex w of G a geometric object $\mathcal {R} (w)$ such that two vertices u and v are adjacent in G if and only if $\mathcal {R} (u)$ and $\mathcal {R} (v)$ intersect. In a contact representation we further require that, for any two vertices u and v, the objects $\mathcal {R} (u)$ and $\mathcal {R} (v)$ have disjoint interiors. The recognition problem asks whether a given graph admits an intersection or contact representation whose sets have a specific geometric shape. Classic examples are interval graphs [1], where the objects are intervals of $\mathbb {R}$, or coin graphs [18], where the objects are interior-disjoint disks in the plane. The partial representation extension problem is a natural generalization of this question where, for each vertex u of a given subset of the vertex set, the geometric object is already prescribed, and the question is whether this partial representation can be extended to a full representation of the input graph. In the last decade the partial representation extension problem has been intensely studied for various classes of intersection graphs, such as (unit or proper) interval graphs [15, 16], circle graphs [6], trapezoid graphs [20], as well as for contact representations [5] and bar-visibility representations [7].

Fig. 1.

A rectangular dual $\mathcal {R}$ for the graph G; the REL $(L_1,L_2)$ induced by $\mathcal {R}$.

Rectangular Duals. In this paper we consider the partial representation extension problem for the following type of representation. A rectangular dual of a graph G is a contact representation $\mathcal {R}$ of G by axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the union of all rectangles is a rectangle; see Fig. 1. We observe that G may admit a rectangular dual only if it is planar and internally triangulated. Furthermore, a rectangular dual can always be augmented with four additional vertices (one on each side) so that only four rectangles touch the outer face of the representation. It is customary that the four vertices on the outer face are denoted by $v_\mathrm {S}$, $v_\mathrm {W}$, $v_\mathrm {N}$, and $v_\mathrm {E}$ corresponding to the geographic directions, and to require that $\mathcal {R} (v_\mathrm {W})$ is the leftmost rectangle, $\mathcal {R} (v_\mathrm {E})$ is rightmost, $\mathcal {R} (v_\mathrm {S})$ is bottommost, and $\mathcal {R} (v_\mathrm {N})$ is topmost; see Fig. 1. We call these vertices the outer vertices and the remaining ones the inner vertices. It is known that a plane internally-triangulated graph has a representation with only four rectangles touching the outer face if and only if its outer face is a 4-cycle and it has no separating triangles, that is, a triangle whose removal disconnects the graph [19]. Such a graph is called a properly-triangulated planar (PTP) graph. Kant and He [14] have shown that a rectangular dual of a given PTP graph G can be computed in linear time.

Historically, rectangular duals have been studied due to their applications in architecture [26], VLSI floor-planning [23, 27], and cartography [12]. Besides the question of an efficient construction algorithm [14], other problems concerning rectangular duals are area minimization [4], sliceability [22], and area-universality, that is, rectangular duals where the rectangles can have any given areas [9]. The latter question highlights the close relation between rectangular duals and rectangular cartograms. Rectangular cartograms were introduced in 1934 by Raisz [25] and combine statistical and geographical information in thematic maps, where geographic regions are represented as rectangles and scaled in proportion to some statistic. There has been lots of work on efficiently computing rectangular cartograms [3, 13, 21]; Nusrat and Kobourov [24] recently surveyed this topic. As a dissection of a rectangle into smaller rectangles, a rectangular dual is also related to other types of dissections, for example with squares [2] or hexagons [8]; see also Felsner’s survey [10].

Fig. 2.

Edge order at the four outer vertices and an inner vertex. (Color figure online)

Regular Edge Labelings. The combinatorial aspects of a contact representation of a graph G can often be described with a coloring and orientation of the edges of G. For example, Schnyder woods describe contact representations of planar graphs by triangles [11]. Such a description also exists for contact representations by rectangles, for example for triangle-free rectangle arrangements [17] or rectangular duals [14]. More precisely, a rectangular dual $\mathcal {R}$ gives rise to a 2-coloring and an orientation of the inner edges of G as follows. We color an edge $\{u, v\}$ blue if the contact between $\mathcal {R} (u)$ and $\mathcal {R} (v)$ is a horizontal line segment, and we color it red otherwise. We orient a blue edge $\{u, v\}$ as (u, v) if $\mathcal {R} (u)$ lies below $\mathcal {R} (v)$, and we orient a red edge $\{u, v\}$ as (u, v) if $\mathcal {R} (u)$ lies to the left of $\mathcal {R} (v)$; see Fig. 1. The resulting coloring and orientation has the following properties:

• 1. All inner edges incident to $v_\mathrm {W}$, $v_\mathrm {S}$, $v_\mathrm {E}$, and $v_\mathrm {N}$ are red outgoing, blue outgoing, red incoming, and blue incoming, respectively.

• 2. The edges incident to each inner vertex form four counterclockwise ordered non-empty blocks of red incoming, blue incoming, red outgoing, and blue outgoing, respectively.

A coloring and orientation with these properties is called a regular edge labeling (REL) or transversal structure. We let $(L_1,L_2)$ denote a REL, where $L_1$ is the set of blue edges and $L_2$ is the set of red edges. Let $L_1(G)$ and $L_2(G)$ denote the two subgraphs of G induced by $L_1$ and $L_2$, respectively. Note that both $L_1(G)$ and $L_2(G)$ are st-graphs, that is, directed acyclic graphs with exactly one source and exactly one sink. It is well known that a PTP graph has a rectangular dual if and only if it admits a REL [14]. A rectangular dual $\mathcal {R}$ realizes a REL $(L_1, L_2)$ if the REL induced by $\mathcal {R}$ is $(L_1, L_2)$. Note that while a rectangular dual uniquely defines a REL, there exist different rectangular duals that realize any given REL.

Partial Rectangular Duals. For a graph G, let E(G) denote the set of edges and V(G) the set of vertices of G. Let U be a subset of V(G). Let G[U] be the subgraph of G induced by U. A partial rectangular dual of G[U] is a contact representation $\mathcal {P}$ that maps each $u \in U$ to an axis-aligned rectangle $\mathcal {P} (u)$. For each $u \in U$, we call $\mathcal {P} (u)$ a fixed rectangle. For a given graph G, a subset U of V(G), and a partial rectangular dual $\mathcal {P}$ of G[U], the partial rectangular dual extension problem asks whether $\mathcal {P}$ can be extended to a rectangular dual $\mathcal {R}$ of G. In particular, for such an extension $\mathcal {R}$ and each $u \in U$, we require that $\mathcal {P} (u) = \mathcal {R} (u)$. In this paper, we study the variant of this problem where we are not only given G, U, and $\mathcal {P}$, but also a REL $(L_1, L_2)$ of G and ask whether there is an extension $\mathcal {R}$ of $\mathcal {P}$ that realizes $(L_1, L_2)$.

Closely related work includes partial representation extension of segment contact graphs [5] and bar-visibility representations [7]. Both problems are NP-complete. However, the hardness reductions crucially rely on low connectivity for choices in the planar embedding. Since PTP graphs are triconnected, they have a unique planar embedding and hence these results cannot be easily transferred.

Contribution and Outline. Our first contribution is a characterization of RELs that admit an extension of a given partial rectangular dual via the existence of what we will call a boundary path set; see Sect. 2. Next, we provide an algorithm that constructs a boundary path set (if possible) as well as an algorithm that computes a representation extension from a boundary path set. Both algorithms run in $\mathcal {O}(nh)$ time, where $n = | V(G) |$ and $h = | U |$, and are detailed in Sect. 3. Finally, we show that by checking only for the existence of a boundary path set, but not explicitly constructing one, we can solve the partial representation extension problem in linear time; see Sect. 4. We summarize our contribution as follows.

Theorem 1

The partial representation extension problem for rectangular duals with a fixed regular edge labeling can be solved in linear time. For yes-instances, an explicit rectangular dual can be constructed within the same time bound.

2 Characterization

In this section, we characterize when a given PTP graph G with REL $(L_1, L_2)$, $U \subset V(G)$, and partial representation $\mathcal {P}$ of G[U] admits an extension $\mathcal {R}$ that realizes $(L_1, L_2)$. Before we can explain our main idea, we require an observation and a few definitions.

Fig. 3.

Dissection of the interior of the frame into (a) vertical and (b) horizontal strips.

We may assume that $v_\mathrm {W}$, $v_\mathrm {S}$, $v_\mathrm {E}$, and $v_\mathrm {N}$ are in U. (Otherwise, we simply place the outer rectangles appropriately around $\mathcal {P}$ such that they touch potential neighbours in $\mathcal {P}$.) The rectangles $\mathcal {P} (v_\mathrm {W})$, $\mathcal {P} (v_\mathrm {S})$, $\mathcal {P} (v_\mathrm {E})$, and $\mathcal {P} (v_\mathrm {N})$ thus form a frame with the area inside partially covered and partially uncovered. To make the question of whether this uncovered area can be filled with the rectangles for $V(G) \setminus U$ more accessible, we subdivide the uncovered area into smaller parts and then try to fill them one by one. More precisely and as illustrated in Fig. 3, we draw a vertical segment through the vertical sides of each fixed rectangle of an inner vertex until another fixed rectangle is hit. This divides the uncovered area inside the frame into vertical strips. We call the fixed rectangles bounding a vertical strip S from below and above the start and end rectangles of S, respectively. We define horizontal strips symmetrically. The start and end rectangle of a horizontal strip are to its left and right, respectively.

The idea for our characterization is as follows. Consider an extension $\mathcal {R}$ of $\mathcal {P}$, where the strips are now filled with rectangles. The vertical strips thus naturally induce subgraphs in $L_1(G)$ containing the vertices that lie inside them plus their start and end rectangle. Together, these subgraphs cover the whole of $L_1(G)$. In particular, for a vertical strip S with start rectangle $\mathcal {P} (u)$ and end rectangle $\mathcal {P} (v)$, the outer face of its induced subgraph consists of a path containing the rectangles along the left side of S and a path along the right side of S. The idea is that, even with $\mathcal {R}$ not known, we have to be able to cover $L_1(G)$ (and $L_2(G)$) with subgraphs defined by pairs of boundary paths. We now make this precise.

Fig. 4.

(a) A boundary path pair for the strip with start rectangle $\mathcal {R} (u)$ and end rectangle $\mathcal {R} (v)$. (b) Neighboring strips can have overlapping boundary paths.

For two paths P and $P'$ in $L_1(G)$, we write $P \preceq P'$ if no vertex of P lies to the right of $P'$, i.e., there is no path from a vertex in $P'$ to a vertex in $P\setminus P'$ in $L_2(G)$. Let S be a vertical strip with start rectangle $\mathcal {P} (u)$ and end rectangle $\mathcal {P} (v)$. A boundary path pair of S is a pair of paths $\langle P_\mathrm {l} (S), P_\mathrm {r} (S)\rangle$ from u to v in $L_1(G)$ such that $P_\mathrm {l} (S) \preceq P_\mathrm {r} (S)$ and $V(P_\mathrm {l} (S) \cup P_\mathrm {r} (S)) \cap U = \{u, v\}$; see Fig. 4(a). Based on the boundary path pair of S, we define $S(L_1(G))$ as the maximal subgraph of $L_1(G)$ that has precisely $P_\mathrm {l} (S)$ and $P_\mathrm {r} (S)$ as the boundary of the outer face. The definitions for horizontal strips, where we order paths $P_\mathrm {b} (S)$ and $P_\mathrm {t} (S)$ from bottom to top, are analogous.

Let $\mathcal {S}_1$ and $\mathcal {S}_2$ be the sets of vertical and horizontal strips, respectively. We define a boundary path set of a REL $(L_1, L_2)$ as a set of boundary path pairs, one for each strip in $\mathcal {S}_1$ and $\mathcal {S}_2$, that satisfy the following properties (see Fig. 4(b)):

(B1):

For strips S and $S'$ in $\mathcal {S}_1$ with S left of $S'$, it holds that $P_\mathrm {r} (S) \preceq P_\mathrm {l} (S')$.

(B2):

For strips S and $S'$ in $\mathcal {S}_2$ with S below $S'$, it holds that $P_\mathrm {t} (S) \preceq P_\mathrm {b} (S')$.

(B3):

The vertical strips cover $L_1(G)$, and the horizontal strips cover $L_2(G)$, that is, $\bigcup _{S \in \mathcal {S}_1} S(L_1(G)) = L_1(G)$ and $\bigcup _{S \in \mathcal {S}_2} S(L_2(G)) = L_2(G)$.

An extension $\mathcal {R}$ of $\mathcal {P}$ directly induces a boundary path set. In the following, we show that the converse is also true.

Theorem 2

Let G be a PTP graph, let $U \subset V(G)$, and let $\mathcal {P}$ be a partial rectangular dual of G[U]. A REL $(L_1, L_2)$ of G admits an extension of $\mathcal {P}$ if and only if $(L_1, L_2)$ admits a boundary path set.

Proof

Suppose that $(L_1, L_2)$ admits a boundary path set. We show how to use this set to construct an extension of $\mathcal {P}$.

Let S be a vertical strip, let $S'$ be a horizontal strip, and assume that $B=S \cap S'$ is nonempty. We call B a box. All such boxes together with $\mathcal {P} (U)$ form a rectangle. We now fill the boxes from the bottom-left to the top-right.

The paths in the pairs $\langle P_\mathrm {l} (S), P_\mathrm {r} (S)\rangle$ and $\langle P_\mathrm {b} (S'), P_\mathrm {t} (S')\rangle$ pairwise intersect in single vertices $v_{\mathrm {l}\mathrm {b}}$, $v_{\mathrm {l}\mathrm {t}}$, $v_{\mathrm {r}\mathrm {b}}$, $v_{\mathrm {r}\mathrm {t}}$. Note that some or even all of these four vertices may coincide. Let $G_B$ be the subgraph of G whose outer cycle is formed by the boundary path pairs between these vertices; see Fig. 5(a). If we enclose $G_B$ appropriately with a 4-cycle, we can apply the algorithm of Kant and He [14] to compute a rectangular dual $\mathcal {R} _B$ of $G_B$.

Fig. 5.

(a) Graph $G_B$ for a box B; (b) representation $\mathcal {R} _B$ for $G_B$; (c) adjusting the left boundary of $\mathcal {R} _B$ to $\mathcal {R} _{B'}$; and (d) adjusting the bottom boundary to $\mathcal {R} (u)$.

By the order in which we fill boxes, we have already treated those immediately to the left and below B; either of them may also be a fixed rectangle. Without loss of generality, we assume that there is a box $B'$ that touches B from the left and a fixed rectangle that touches B from below.

First, we modify $\mathcal {R} _B$ such that it fits to the rectangular dual $\mathcal {R} _{B'}$ that is drawn inside of $B'$. Property (B1) of a boundary path set ensures that the rectangles in $\mathcal {R} _{B'}$ that are adjacent to the right side of $\mathcal {R} _{B'}$ are “compatible” to the rectangles in $\mathcal {R} _B$ that are adjacent to the left side of $\mathcal {R} _B$. Hence, starting with a tiny version of $\mathcal {R} _B$ placed in the lower left corner of B, we can stretch $\mathcal {R} _B$ vertically along suitable horizontal cuts such that, for every vertex u in $V(G_{B'}) \cap V(G_B)$, the left piece of $\mathcal {R} (u)$ (in $B'$) and the right piece of $\mathcal {R} (u)$ (in B) fit together; see the green rectangle g in Fig. 5(b)–(c).

Now suppose that, for some vertex $u \in U$, the fixed rectangle $\mathcal {P} (u)$ bounds B from below. Property (B3) of a boundary path set ensures that if we stretch $\mathcal {R} _B$ horizontally along some vertical cut, then we have the correct horizontal contacts with $\mathcal {P} (u)$; see the yellow rectangle y in Fig. 5(c)–(d).

Finally, note that property (B3) ensures that, at the end of this construction, every vertex of G is represented by a rectangle in $\mathcal {R}$.    $\square$

Fig. 6.

A rectangular dual with a boundary path set of size $\mathcal {O}(nh)$.

We close this section with an observation about the potential size of boundary path sets. As we have noted above, a vertex may lie on multiple boundary paths; in fact, it may even lie on all of them as the example in Fig. 6 shows. Hence, the size of a boundary path set can be in $\varOmega (nh)$, where $n = |V(G)|$ and $h = |U|$.

3 Finding a Boundary Path Set

We now show how to compute a boundary path set for a given REL $(L_1, L_2)$ and a partial representation $\mathcal {P}$. The idea is as follows. As we did for the boxes in the proof of Theorem 2, we handle the vertical strips in $\mathcal {S}_1$ from bottom-left to top-right. When computing the boundary path pair for a vertical strip $S \in \mathcal {S}_1$, we want the resulting graph $S(L_1(G))$ to include all necessary vertices but otherwise as few vertices as possible. In particular, there may be rectangles that by $(L_1, L_2)$ need to have their left boundary align with the left boundary of S and thus need to be in $P_\mathrm {l} (S)$. To make this more precise, let $\mathcal {P} (v_1), \mathcal {P} (v_2), \ldots , \mathcal {P} (v_k)$ be the fixed rectangles whose right sides touch the left side of S. Let x be a vertex that lies on a path from u to v in $L_1(G)$. Then we say x is left-bounded in S if and only if one of the following conditions applies (see Fig. 7(a)):

(L1):

$x = u$ or $x = v$ and the left side of $\mathcal {P} (x)$ aligns with the left side of S;

(L2):

$(v_i, x)$, for some $i \in \{1, \ldots , k\}$, is an edge in $L_2(G)$;

(L3):

(y, x) is the leftmost outgoing edge of y and the leftmost incoming edge of x in $L_1(G)$, and y is left-bounded;

(L4):

(x, y) is the leftmost outgoing edge of x and the leftmost incoming edge of y in $L_1(G)$, and y is left-bounded.

Condition (L2) applies if $\mathcal {R} (x)$ has to be directly to the right of a fixed rectangle left of S. Condition (L3) and (L4) apply if the left side of $\mathcal {R} (x)$ has to align with the left side of a left-bounded rectangle R(y) directly above or below, respectively. Note that in this case there exists also a vertex $y'$ that is right-bounded in a strip $S'$ left of S and $(y', x) \in E(L_2(G))$.

Fig. 7.

(a) Vertex u is left-bounded in S on Condition (L1), c on Condition (L2), a on Condition (L3), and b is not left-bounded; (b) vertex c is right-bounded in $S'$ on Condition (R2), and a and b on Condition (R3); (c) $S''$ has neither left- nor right-bounded vertices except for u and v.

Next, let $\mathcal {P} (v_1'), \mathcal {P} (v_2'), \ldots , \mathcal {P} (v_k')$ be the fixed rectangles whose left sides touch the right side of S. Then x is right-bounded in S if and only if one of the following conditions applies (see Fig. 7(b)):

(R1):

$x = u$ or $x = v$ and the right side of $\mathcal {P} (x)$ aligns with the right side of S;

(R2):

$(x, v_i')$, for some $i \in \{1, \ldots , k\}$, is an edge in $G_2$;

(R3):

(y, x) is the rightmost outgoing edge of y and the rightmost incoming edge of x in $L_1(G)$, and y is right-bounded;

(R4):

(x, y) is the rightmost outgoing edge of x and the rightmost incoming edge of y in $L_1(G)$, and y is right-bounded.

Note that x can be both left- and right-bounded. Furthermore, starting from $u,v'_1,\dots ,v'_k,v$, these conditions can easily be checked for each strip. Overall, we can thus find all left- and right-bounded vertices of all strips in $\mathcal {O}(n)$ time.

Theorem 3

Let G be a PTP graph with n vertices and REL $(L_1, L_2)$, let $U \subset V(G)$, let $h = |U|$, and let $\mathcal {P}$ be a partial rectangular dual of G[U].

In $\mathcal {O}(nh)$ time, we can decide whether $(L_1, L_2)$ admits a boundary path set with respect to $\mathcal {P}$ and, in the affirmative, compute it.

Proof

We show how to compute the boundary path pairs for vertical strips; horizontal strips can be treated analogously. Let $\mathcal {S}_1^\checkmark \!$ be the strips in $\mathcal {S}_1$ that have already been processed. Let S be a strip with start rectangle $\mathcal {P} (u)$ and end rectangle $\mathcal {P} (v)$ such that every strip left of S is in $\mathcal {S}_1^\checkmark \!$.

An edge (x, y) of $L_1(G)$ is suitable if one of the following conditions applies:

(E1):

$y = v$;

(E2):

$y \in P_\mathrm {r} (S')\setminus U$, where $S' \in \mathcal {S}_1^\checkmark \!$ is directly left of S and y is not right-bounded in $S'$;

(E3):

$y \not \in U$ and (x, y) is not an edge of $\mathcal {S}_1^\checkmark \! (L_1(G))$.

Condition (E2) means that $\mathcal {R} (y)$ can span from $S'$ into S since it is not right-bounded in $S'$. Thus, in Fig. 7(a) (w, x) is suitable but $(x, y')$ is not. Furthermore, (z, v) is suitable by Condition (E1), and (u, w), (w, x), and (y, z) are suitable by Condition (E3). Note that $P_\mathrm {l} (S)$ may only use suitable edges. Hence, to compute $P_\mathrm {l} (S)$, we can start at u and always add the leftmost suitable outgoing edge until we reach v. It follows that if, at some point, there is no suitable edge available, then $(L_1, L_2)$ does not admit a boundary path set. Taking the leftmost suitable outgoing edge ensures that $P_\mathrm {l} (S)$ passes through all left-bounded vertices in S.

We now show how to construct $P_\mathrm {r} (S)$, enforcing that all right-bounded vertices lie on $P_\mathrm {r} (S)$. We thus start with the set of disjoint subpaths $P_1, P_2, \ldots , P_k$ induced by u, the right-bounded vertices, and v ordered from bottom to top; see Fig. 8(a). Note that for a right-bounded vertex x its rightmost outgoing edge also has to be in $P_\mathrm {r} (S)$, unless $x = v$, and its rightmost incoming edge also has to be in $P_\mathrm {r} (S)$, unless $x = u$. Therefore, we extend each subpath with these rightmost outgoing and incoming edges; see Fig. 8(b). For $i \in \{1, \dots , k-1\}$, we then simultaneously extend $P_i$ and $P_{i+1}$ by always taking the leftmost suitable outgoing and incoming edge, respectively, but without crossing $P_\mathrm {l} (S)$. If the extensions of $P_i$ and $P_{i+1}$ meet, we join them; see Fig. 8(c). Otherwise, both extensions will stop (due to a lack of suitable edges). In this case there is no path $P_\mathrm {r} (S)$, and then the REL $(L_1, L_2)$ does not admit a boundary path set.

Fig. 8.

Computation of $P_\mathrm {r} (S)$ (a) starting with subpaths induced by u, right-bounded vertices and v, (b) extending these subpaths with their rightmost predecessor and successor, and (c) leftwards until they meet. (Extensions downwards are shown green.) (Color figure online)

Once $P_\mathrm {l} (S)$ and $P_\mathrm {r} (S)$ have been computed successfully, we update the edge set of $\mathcal {S}_1^\checkmark \! (L_1(G))$ before processing the next strip.

The runtime is linear in the size of the boundary path set, that is, $\mathcal {O}(nh)$.    $\square$

Next, we show how to obtain an extension of $\mathcal {P}$ from a boundary path set.

Theorem 4

Let G be a PTP graph with n vertices and REL $(L_1, L_2)$, let $U \subset V(G)$, let $h = |U|$, and let $\mathcal {P}$ be a partial rectangular dual of G[U]. Given a boundary path set of $(L_1, L_2)$, we can find an extension of $\mathcal {P}$ in $\mathcal {O}(nh)$ time.

Proof

In the proof of Theorem 2, we gave an algorithm that finds for every box B the graph $G_B$ of vertices whose rectangles (partially) lie inside or on the boundary of B. The algorithm computes a rectangular dual of $G_B$, which requires $\mathcal {O}(|V(G_B)|)$ time per box [14], and then fits each dual into the extension built so far, which can also be done in $\mathcal {O}(|V(G_B)|)$ time per box.

We now argue that $\sum _B |V(G_B)| = \mathcal {O}(nh)$. Namely, a box B either lies completely inside a rectangle, in which case $|V(G_B)| = 1$, or it contains part of the boundary of every rectangle that corresponds to a vertex in $V(G_B)$. For any vertex $v \in V(G) \setminus U$, each of the four boundary sides of $\mathcal {R} (v)$ lies either inside a single strip or on the boundary between two strips, so the boundary of $\mathcal {R} (v)$ can lie in only $\mathcal {O}(h)$ boxes in total. As there are $\mathcal {O}(h^2)$ boxes, we have $\sum _B |V(G_B)| \in \mathcal {O}(h^2 + nh) = \mathcal {O}(nh)$.    $\square$

4 Linear-Time Algorithm

Explicitly constructing a boundary path set, as in Theorem 3, requires time proportional in the size of the set, which can however be in $\varOmega (nh)$. In this section, we show that even without an explicit construction, we can decide if a boundary path set exists, and if so, compute an extension. Both the decision and the computation can be done in linear time.

Our approach relies on the following observations. Suppose a boundary path set exists. Let v be a vertex in $V(G) \setminus U$ that lies on a boundary path of vertical strips $S_1, \ldots , S_k$, ordered from left to right. Then the left boundary of $\mathcal {R} (v)$ lies in $S_1$ and the right boundary in $S_k$. Thus, to compute the x-coordinates of $\mathcal {R} (v)$, it suffices to know the leftmost and the rightmost boundary path on which v lies. Instead of constructing all boundary path pairs of vertical strips, we only construct the subgraph $H_1$ of $L_1(G)$ induced by U and the vertices on the boundary path pairs. We call $H_1$ the vertical boundary graph of $(L_1, L_2)$. Furthermore, for each edge e in $H_1$, we store the leftmost and the rightmost strip for which e lies on a boundary path. Note that as $H_1$ is a subgraph of $L_1(G)$, the size of $H_1$ is in $\mathcal {O}(n)$. Analogously, we define $H_2$ for the horizontal strips.

Before we show how to construct the boundary graphs $H_1$ and $H_2$, we prove that they suffice to compute an extension of $\mathcal {P}$.

Lemma 5

Let G be a PTP graph with n vertices, let $U \subset V(G)$, let $\mathcal {P}$ be a partial representation of G[U] and $(L_1, L_2)$ a REL of G. If boundary graphs $H_1$ and $H_2$ of $(L_1, L_2)$ are given, then an extension of $\mathcal {P}$ that realizes $(L_1, L_2)$ can be computed in $\mathcal {O}(n)$ time.

Proof

We show how to compute the x-coordinates of rectangles using $H_1$; the y-coordinates can be computed analogously with $H_2$. The idea is to compute a rectangular dual for each inner face of $H_1$, which in total will yield a full rectangular dual. Note that the boundary of each face of $H_1$ consists of two directed paths between a start and an end vertex. Therefore, each face has a single source, a single sink, a left path, and a right path.

We distinguish two types of inner faces of $H_1$, namely, whether they describe a region inside a strip or a part of the boundary of a strip. A face f of the latter type can be identified by the occurrence of a right-bounded vertex v on the left path of f where v is not the source or sink of f; see Fig. 9(a). Note that in this case all inner vertices of the left path of f are right-bounded and all inner vertices of the right path of f are left-bounded. We then set the right x-coordinate of every inner vertex on the left path and the left x-coordinate of every inner vertex on the right path to the x-coordinate of the respective boundary of the strip.

Otherwise, an inner face f of $H_1$ describes a region inside a strip of S; see Fig. 9(b). We define the graph $G_f$ as the subgraph of G with all vertices that lie on or inside the cycle that is defined by f. By adding an outer four-cycle appropriately, we obtain a rectangular dual $\mathcal {R} _f$ of $G_f$ with the algorithm by Kant and He [14]. We then scale $\mathcal {R} _f$ to the width of S and set the x-coordinates for the vertices in $G_f$ inside S accordingly, that is, the right x-coordinate for the vertices on the left path of f, the left x-coordinate for vertices on the right path of f, and both x-coordinates for interior vertices of $G_f$.

After we have processed all faces, both x-coordinates of all vertices are set since each vertex is either fixed, has a face to the left and a face to the right, or lies inside a face. Since the faces are ordered from left to right in accordance with their respective strips, the computed x-coordinates of the rectangles also form the correct horizontal adjacencies. We repeat this process with $H_2$ to compute the y-coordinates and thus to obtain also the correct vertical adjacencies.

Processing a face f takes time linear in the size of $G_f$. Hence, the total running time is linear in the size of $L_1(G)$ and $L_2(G)$, and thus in $\mathcal {O}(n)$.    $\square$

Fig. 9.

Correspondence between a face of $H_1$ and (a) a part of the boundary of a strip or (b) a region inside a strip; extending $H_1$ with (c) $P_\mathrm {l} (S)$ and (d) $P_\mathrm {r} (S)$.

Lemma 6

Let G be a PTP graph with n vertices, let $U \subset V(G)$, let $\mathcal {P}$ be a partial representation of G[U] and $(L_1, L_2)$ a REL of G. In $\mathcal {O}(n)$ time, we can decide whether $(L_1, L_2)$ admits a boundary path set with respect to $\mathcal {P}$ and, in the affirmative, compute boundary graphs $H_1$ and $H_2$.

Proof

As in the proof of Theorem 3, we focus again on vertical strips and process them from bottom-left to top-right. Let $\mathcal {S}_1^\checkmark \!$ be the strips in $\mathcal {S}_1$ that have already been processed. Let S be a strip with start rectangle $\mathcal {P} (u)$ and end rectangle $\mathcal {P} (v)$ such that every strip left of S is in $\mathcal {S}_1^\checkmark \!$. The idea is to only compute the parts of $P_\mathrm {l} (S)$ that do not coincide with a boundary path of a strip $S' \in \mathcal {S}_1^\checkmark \!$ and the parts of $P_\mathrm {r} (S)$ that do not coincide with $P_\mathrm {l} (S)$. Initially, set $H_1$ as $L_1(G)[U]$.

We start with $P_\mathrm {l} (S)$; see Fig. 9(c). Observe that $P_\mathrm {l} (S)$ should only consist of u, vertices left-bounded in S, v, and vertices on paths $P_\mathrm {r} (S')$ for $S' \in \mathcal {S}_1^\checkmark \!$. Let $P_1, \ldots , P_k$ be the subpaths induced by u, vertices left-bounded in S, and v. Let $x_i$ be the first vertex of $P_i$ and $y_i$ the last. Further let $(w_i, x_i)$ be the leftmost incoming edge of $x_i$ and let $(y_i, z_i)$ be the leftmost outgoing edge of $y_i$. For $i \in \{2, \ldots , n\}$, $w_i$ already has to be in $H_1$ but not in U; otherwise $P_\mathrm {l} (S)$ does not exist. The analogous condition needs to hold for $(y_i, z_i)$. If this holds for each $i \in \{1, \ldots , k\}$, we add the vertices and edges in each $P_i$ as well as the edges $(w_i, x_i)$ and $(y_i, z_i)$ to $H_1$. Finally, we can test that the $P_i$’s are in the correct order in $H_1$ with an st-ordering of $L_1(G)$.

Checking the existence of $P_\mathrm {r} (S)$ works like the construction in Theorem 3; see Fig. 9(d). Recall that we extended subpaths induced by u, right-bounded vertices, and v, first with right-most incoming and outgoing edges appropriately, and then tried to join subsequent subpaths by taking the left-most outgoing and incoming edges, respectively. Observe that reaching $P_\mathrm {l} (S)$ during such an extension, now means that we encounter a vertex in $H_1 \setminus U$; see Fig. 9. Hence, here we stop extensions when encounter a vertex v that is already in $H_1$ but not in U. If connecting the subpaths to each other or $H_1$ is successful, we test their order again with an st-ordering of $L_1(G)$ and finally add them to $H_1$.

During the construction of $H_1$ we also need to label the faces with the strips they belong to. Therefore when a subpath $P_i$, for $i \in \{1, \ldots , k-1\}$, is added to $H_1$ as part of a left boundary path $P_\mathrm {l} (S)$, we tell its left face that is lies on the left boundary of S. For any subpath added to $H_1$ as part of a right boundary path $P_\mathrm {r} (S)$, we tell its left face that it lies inside S.

Lastly, note that the running time is linear in the size of $H_1$, $H_2$ and G.    $\square$

As a result of Lemmas 5 and 6 we get our main result, Theorem 1.

Theorem 1

The partial representation extension problem for rectangular duals with a fixed regular edge labeling can be solved in linear time. For yes-instances, an explicit rectangular dual can be constructed within the same time bound.

5 Concluding Remarks

We have characterized the partial rectangular duals that admit an extension realizing a given REL in terms of boundary path sets. Based on this, we have given an algorithm that computes an extension, if it exists, in time proportional to the size of the boundary path set. We have sped up this algorithm by considering only the underlying simple graph of a boundary path set – the boundary graph.

The partial rectangular dual extension problem remains open when no REL is specified. Eppstein et al. [9] gave algorithms that compute constrained area-universal rectangular duals and solved the extension problem for RELs. A partial rectangular dual induces a partial REL. Hence an extension of a partial rectangular dual $\mathcal {P}$ can be found by computing every extension of this partial REL and by testing for each whether it admits an extension of $\mathcal {P}$, using our linear-time algorithm. There can, however, be exponentially many extensions of a partial REL. We are interested in a faster approach.