Planar Straight-Line Realizations of 2-Trees with Prescribed Edge Lengths

Abstract

We study a classic problem introduced thirty years ago by Eades and Wormald. Let $G=(V,E,\lambda )$ be a weighted planar graph, where $\lambda : E \rightarrow \mathbb {R}^+$ is a length function. The Fixed Edge-Length Planar Realization problem (FEPR for short) asks whether there exists a planar straight-line realization of G, i.e., a planar straight-line drawing of G where the Euclidean length of each edge $e \in E$ is $\lambda (e)$. Cabello, Demaine, and Rote showed that the FEPR problem is -hard, even when $\lambda$ assigns the same value to all the edges and the graph is triconnected. Since the existence of large triconnected minors is crucial to the known -hardness proofs, in this paper we investigate the computational complexity of the FEPR problem for weighted 2-trees, which are $K_4$-minor free. We show its -hardness, even when $\lambda$ assigns to the edges only up to four distinct lengths. Conversely, we show that the FEPR problem is linear-time solvable when $\lambda$ assigns to the edges up to two distinct lengths, or when the input has a prescribed embedding. Furthermore, we consider the FEPR problem for weighted maximal outerplanar graphs and prove it to be linear-time solvable if their dual tree is a path, and cubic-time solvable if their dual tree is a caterpillar. Finally, we prove that the FEPR problem for weighted 2-trees is slice-wise polynomial in the length of the longest path.

This research was partially supported by MIUR Project “AHeAD” under PRIN 20174LF3T8, by H2020-MSCA-RISE project 734922 – “CONNECT”, and by Roma Tre University Azione 4 Project “GeoView”.

1 Introduction and Preliminary Results

The problem of producing drawings of graphs with geometric constraints is a core topic for Graph Drawing [3,4,5, 11, 14, 23, 24, 27, 34, 43, 45]. In this context, a classic question is the one of testing if a planar graph can be drawn planarly and straight-line with prescribed edge lengths. The study of such a question is related to several topics in computational geometry [17, 41, 47], rigidity theory [16, 30, 32], structural analysis of molecules [8, 31], and sensor networks [13, 38, 40]. Formally, given a weighted planar graph $G=(V,E,\lambda )$, i.e., a planar graph equipped with a $\lambda : E \rightarrow \mathbb {R}^+$, the Fixed Edge-Length Planar Realization problem (FEPR for short) asks whether there exists a of G (PR for short), i.e., a planar straight-line drawing of G where the Euclidean length of each edge $e \in E$ is $\lambda (e)$. The FEPR problem was first studied by Eades and Wormald [26], who showed its -hardness for triconnected planar graphs and for biconnected planar graphs with unit lengths. Cabello, Demaine, and Rote strengthened this result by proving -hardness for triconnected planar graphs with unit lengths [12]. Abel et al. [1] proved the $\exists \mathbb {R}$-completeness of the FEPR problem with unit lengths, solving a problem posed by Schaefer [42].

Fig. 1.

A planar and a non-planar straight-line realization of the same 2-tree.

Since large triconnected minors are essential in the known -hardness proofs of the FEPR problem, we study its complexity for 2-trees, which are the maximal graphs with no K$_4$-minor. A is a graph composed of 3-cycles glued together along edges in a tree-like fashion; see Fig. 1, where we show a planar and a non-planar realization of a weighted 2-tree. Every 2-tree is planar and biconnected, and the class of 2-trees is the class of maximal series-parallel graphs. There is a vast amount of research on 2-trees in Graph Drawing (e.g., in [18, 25, 28, 33, 39]). The edge lengths of 2-trees have been studied in [9, 10].

In this paper, we first show that the FEPR problem can be solved in linear time for 2-trees with prescribed embedding¹. We note the FEPR problem is -hard for general planar graphs with a prescribed embedding [12]. Second, we show that, in the variable embedding setting, the FEPR problem is -hard when the number of distinct lengths is at least four, whereas it is linear-time solvable when the number of distinct lengths is one or two. Note that, for general planar graphs, the problem is -hard even when all the edges are required to have the same length [26]. Third, we deal with maximal outerplanar graphs. We show that the FEPR problem can be solved in linear time for maximal outerpaths, i.e., the maximal outerplanar graphs whose dual tree is a path, and in cubic time for maximal outerpillars, i.e., the maximal outerplanar graphs whose dual tree is a caterpillar. Finally, we present a slice-wise polynomial algorithm for 2-trees, parameterized by the length of the longest path.

Because of space limitations, several proofs are omitted. They can be found in the full version of the paper [2].

Preliminaries. We assume familiarity with Graph Drawing (see, e.g., [21]). A planar drawing of a graph G defines a clockwise order of the edges incident to each vertex of G; the set of such orders for all the vertices is a for G. Two planar drawings of G are if (i) they define the same rotation system for G and (ii) their outer faces have the same boundaries. An equivalence class of planar drawings is a (or simply an ). When referring to a planar drawing $\varGamma$ of a graph that has a prescribed embedding $\mathcal E$, we always imply that $\varGamma$ respects $\mathcal E$; sometimes, we explicitly stress this.

An is a planar drawing in which all the vertices are incident to the outer face. An is an equivalence class of outerplanar drawings. An is a graph that admits an outerplanar drawing. The T of a biconnected outerplanar graph G is defined as follows. Consider the (unique) outerplane embedding $\mathcal O$ of G. Then T has a node for each internal face of $\mathcal O$ and has an edge between two nodes if the corresponding faces of $\mathcal O$ are incident to the same edge of G. An is a biconnected outerplanar graph whose dual tree is a path. A is a tree that becomes a path if its leaves are removed. An is a biconnected outerplanar graph whose dual tree is a caterpillar.

Fig. 2.

A 2-tree and its decomposition tree rooted at the 3-cycle with label 1.

A is recursively defined as follows. A 3-cycle is a 2-tree. Given a 2-tree G containing an edge (u, w), the graph obtained by adding to G a vertex v and two edges (v, u) and (v, w) is a 2-tree. We observe that the neighbors of any degree-2 vertex are adjacent. The tree-like structure of a 2-tree G is encoded by means of the T a 3-cycle of G. Each node in T represents a 3-cycle of G, and two nodes are adjacent if their corresponding 3-cycles share an edge; see Fig. 2. The decomposition tree of a 2-tree is easily computed in linear time. We adopt the Euclidean metric and assume that the length function of G is such that every 3-cycle satisfies the triangle inequality. This is a necessary condition for the existence of a of G, i.e., a (not necessarily planar) drawing of G in which each edge is represented by a line segment with the prescribed length. We often refer to 3-cycles of G, nodes of T, and triangles in a straight-line realization of G interchangeably.

Prescribed Embedding. First, we deal with 2-trees with a prescribed rotation system or embedding. We start by presenting a geometric tool.

Theorem 1

Let G be an n-vertex weighted 2-tree, $\mathcal {E}$ be a plane embedding (resp. $\mathcal R$ be a rotation system) for G, and $\varGamma$ be a straight-line realization of G. There is an O(n)-time algorithm to test whether $\varGamma$ is a PR respecting $\mathcal {E}$ (resp. $\mathcal R$).

The proof of Theorem 1 is based on an algorithm that: i. tests if $\varGamma$ respects $\mathcal E$ (resp. $\mathcal {R}$), ii. triangulates the faces of $\varGamma$ and checks if they are simple polygons [15], and iii. tests if the obtained drawing is a convex subdivision [20].

We now present our prescribed embedding result.

Theorem 2

Let G be an n-vertex weighted 2-tree and $\mathcal {E}$ be a plane embedding (resp. $\mathcal R$ be a rotation system) for G. There is an O(n)-time algorithm to test whether G admits a PR that respects $\mathcal {E}$ (resp. $\mathcal R$) and to construct one, if any.

The proof of Theorem 2 is based on: i. computing a decomposition tree T rooted at the 3-cycle c of G with the largest sum of the edge lengths; ii. computing a candidate PR $\varGamma$ by visiting T in pre-order while greedily adding to $\varGamma$ the drawing of each 3-cycle t, by exploiting $\mathcal E$ (resp. $\mathcal R$) and the containment relationship between c and t; and iii. testing whether $\varGamma$ is a PR of G whose plane embedding (resp. rotation system) is $\mathcal E$ (resp. $\mathcal {R}$) by means of Theorem 1.

2 NP-Hardness for 2-Trees with 4 Edge Lengths

We sketch a reduction from the -complete Planar Monotone 3-SAT problem [7] (PMS for short) to the FEPR problem with four edge lengths.

Theorem 3

The FEPR problem is -hard for weighted 2-trees, even for instances whose number of distinct edge lengths is 4.

Fig. 3.

(a) The monotone rectilinear representation $\varGamma _\phi$ of $G_\phi$, and (b) Its modified version $\varGamma ^*_\phi$. (c) Overview of the reduction showing only the frame triangles (Color figure online).

A Boolean CNF formula $\phi$ is an instance of PMS if the variable-clause incidence graph $G_\phi$ of $\phi$ is planar, and each clause of $\phi$ is either (it consists of positive literals) or (it consists of negated literals). The PMS problem is -complete even when $G_\phi$ comes with a  [7], i.e., a crossing-free drawing $\varGamma _{\phi }$ of $G_\phi$ in which i. variables and clauses are boxes, ii. edges are vertical segments, and iii. positive (resp. negative) clauses lie above (resp. below) the horizontal strip containing the variable boxes; see Fig. 3(a).

First, we transform $\varGamma _\phi$ into a representation $\varGamma ^*_\phi$ of $G_\phi$ that uses segments with slope $0^\circ$, $60^\circ$, or $90^\circ$; see Fig. 3(b). Then we obtain from $\varGamma ^*_\phi$ a weighted 2-tree $H_\phi$ that admits a PR if and only if $\phi$ is satisfiable; see Fig. 3(c). The edges of $H_\phi$ are assigned the lengths $w_1=1$, $w_2=0.9$, $w_3=0.2$, and $w_4=1.61$. To obtain $H_\phi$ we construct gadgets for the variables, the clauses, and the edges of $G_\phi$. Our gadgets exploit two main types of triangles: equilateral triangles with sides of length $w_1$ ( ), and isosceles triangles with base of length $w_1$ and two sides of length $w_2$ ( ). The union of the frame triangles of the gadgets representing variables (gray), edges (yellow), and clauses (green), together with a set of frame triangles connecting the variable gadgets (blue), forms a maximal outerplanar graph. Since this graph is formed by frame triangles, it has a unique PR up to rigid transformations.

Fig. 4.

The $(\alpha ,\beta )$-clause gadget with $\alpha =4$ and $\beta =2$. The values of $\alpha$ and $\beta$ depend on the relative positions in $\varGamma ^*_\phi$ of the involved variable gadgets (Color figure online).

Our strategy is to construct $H_\phi$ from a “rigid” part (mainly formed by the union of the frame triangles of the gadgets), and a part that instead allows for different embedding choices (mainly encoded by the flips of transmission triangles). Consider for example Fig. 4, where we illustrate the PR of a clause gadget, which is the most critical gadget in the construction. Each transmission triangle $\triangle$ (in red) has two possible different embeddings. The choice of this embedding influences the choice of the embeddings of the transmission triangles that “conflict” with $\triangle$, that is, that overlaps with $\triangle$ in one of their embeddings. These chains of conflict relationships allow for “truth values” that come from the variable gadgets to “move” along the gadgets representing edges. The relevant triangles $\triangle ^1_\text {IN}$, $\triangle ^2_\text {IN}$, and $\triangle ^3_\text {IN}$ encode such values: In Fig. 4, $\triangle ^1_\text {IN}$ and $\triangle ^2_\text {IN}$ point downward since the corresponding variable is $\texttt {True}$, and $\triangle ^3_\text {IN}$ points upward since the corresponding variable is $\texttt {False}$. A special set of transmission triangles, whose flip depends on the orientation of the relevant triangles, overlap in the pink hexagonal region if all the relevant triangles point upward. Conversely, if at least one relevant triangle points downward, the clause gadget admits a PR.

3 Linear-Time Algorithm for 2-Trees with 2 Edge Lengths

This section is devoted to sketch the proof of the following theorem.

Theorem 4

Let $G=(V,E,\lambda )$ be an n-vertex weighted 2-tree, where $\lambda : E \rightarrow \{ w_1, w_2 \}$ with $w_1,w_2\in \mathbb {R}^+$. There is an O(n)-time algorithm to test whether G admits a PR and to construct one, if any.

Let $\varGamma$ be a PR of G. If $w_1 = w_2$, then the existence of $\varGamma$ implies that G is an outerplanar graph, which is a linear-time testable property [19, 36, 46], and that $\varGamma$ is outerplanar. Since G is 2-connected, it has a unique outerplane embedding $\mathcal E$ which can be constructed in linear time [19, 36, 37, 44, 46]. Hence, the problem reduces to the problem of testing whether G has a PR that respects $\mathcal E$, which can be solved in linear time by Theorem 2.

Consider now the case in which $w_1\ne w_2$. W.l.o.g. assume $w_1 < w_2$. Also, let $r=\frac{w_2}{w_1} > 1$. The realization of any 3-cycle of G is one of the following types of triangles: i. an equilateral ( ) triangle of side $w_1$, ii. an equilateral ( ) triangle of side $w_2$, iii. an isosceles ( ) triangle with base $w_1$ and two sides of length $w_2$, and iv. an isosceles ( ) triangle with base $w_2$ and two sides of length $w_1$; refer to Fig. 5.

Fig. 5.

The four possible types of triangles that represent the 3-cycles of G.

Let $\triangle _1$ and $\triangle _2$ be two triangles realizing two different 3-cycles in a PR of G. We say that $\triangle _1$ is $\triangle _2$ if all the points of $\triangle _1$ are points of $\triangle _2$ and at least one vertex of $\triangle _1$ is an interior point of $\triangle _2$. Let T be the decomposition tree of G. We have the following.

Lemma 1

If T is rooted at the 3-cycle with the largest sum of edge lengths and $\triangle _1$ is drawn inside $\triangle _2$, then $\triangle _1$ is a leaf triangle that shares a side with $\triangle _2$.

By Lemma 1, we assume that T is rooted at a 3-cycle with the largest sum of edge lengths. The of G is the subgraph $G_F \subseteq G$ obtained, in linear time, as follows: For each leaf triangle $\triangle _i$ that can be drawn inside its parent or a sibling triangle $\triangle _j$, we remove from G the vertex v that $\triangle _i$ does not share with $\triangle _j$, along with the two edges incident to v. Note that i. $G_F$ is a 2-tree which may contain any type of triangle, ii. by Lemma 1, no triangle of $G_F$ is drawn inside any other triangle in any PR of G, and iii. T is rooted at a triangle of the framework. We test in linear time if $G_F$ is outerplanar and, in such case, we compute in linear time its unique outerplanar embedding $\mathcal E$. Exploiting Theorem 2, we test if $G_F$ admits a PR respecting $\mathcal E$. In the negative case G admits no PR, otherwise we denote by $\varGamma _F$ the obtained PR of $G_F$. Hereafter, we assume that $\varGamma _F$ exists.

Refer to Fig. 6, where we show an example of a PR of a weighted 2-tree. Let $L_{\triangle }$ be the set of leaf triangles that were removed from G to obtain $G_F$. Observe that $L_{\triangle }$ is formed by small equilateral and flat isosceles triangles. We show how to extend $\varGamma _F$ to a PR of G by embedding the triangles of $L_{\triangle }$, if possible. Let $\triangle$ denote a triangle in $L_{\triangle }$. The triangle $\triangle$ has a side in $G_F$ that is incident to either two internal faces, or to an internal face and the outer face of $\varGamma _F$; hence $\triangle$ has exactly two embedding choices. We say that $\triangle$ has an if it is embedded inside an internal face of $\varGamma _F$, and an otherwise. We say that $\triangle$ induces a if it has an outer embedding and $\varGamma _F \cup \triangle$ is not planar; e.g., see the (dashed) outer embedding of $\triangle _{16}$ in Fig. 6. Let $\triangle _i$ and $\triangle _j$ be two triangles of $L_{\triangle }$. We say that $\triangle _i$ and $\triangle _j$ induce an if both have an internal embedding and $\varGamma _F \cup \triangle _i \cup \triangle _j$ is not planar; e.g., see the (dashed) internal embedding of $\triangle _{9}$ and the (solid) internal embedding of $\triangle _{18}$. On the other hand, we say that $\triangle _i$ and $\triangle _j$ induce an if both have an outer embedding and $\varGamma _F \cup \triangle _i \cup \triangle _j$ is not planar; e.g., see the (dashed) outer embeddings of $\triangle _{6}$ and $\triangle _{13}$.

Fig. 6.

(Left) A PR of a weighted 2-tree G. Dashed triangles represent alternative embeddings for some 3-cycles, which would generate conflicts. (Right) The decomposition tree of G rooted at the framework triangle $\triangle _1$. Triangles of $\varGamma _F$ are thick, and edges of the leaf triangles of $L_{\triangle }$ that are not in $\varGamma _F$ are thin.

Lemma 2

Let $\triangle _i$ and $\triangle _j$ be two leaf triangles of $L_{\triangle }$ that can both be drawn inside some triangle $\triangle \in \varGamma _F$. The triangles $\triangle _i$ and $\triangle _j$ induce an internal conflict if at least one of the following properties holds true:

• (a) $\triangle _i$ and $\triangle _j$ share an edge;

• (b) $\sqrt{3} < r \le 2 \cos (\pi /12)$ and $\triangle$ is a tall isosceles;

• (c) $1 < r \le \sqrt{3}$.

The weighted 2-tree shown in Fig. 6 is such that $\sqrt{3}< r \le 2 \cos (\pi /12)$, that is $r < 2$. By Property b of Lemma 2, two flat isosceles triangles can be drawn inside a big equilateral triangle without inducing conflicts, and any pair of leaf triangles (i.e., either two flat isosceles triangles or a flat isosceles triangle and a small equilateral triangle) induce an internal conflict inside a tall isosceles triangle. On the other hand, by Property a of Lemma 2 and the fact every triangle in $L_\triangle$ has two embedding choices, for a PR of G to exist, it must hold that no three triangles in $L_{\triangle }$ share the same edge with a triangle of $G_F$. If $L_{\triangle }$ satisfies this requirement, then we say that $L_{\triangle }$ is .

Lemma 3

If $L_{\triangle }$ is consistent, then there are O(1) pairs of triangles sharing an edge with the same triangle of $G_F$ that induce an internal conflict.

Proof

By Lemma 1, two triangles of $L_\triangle$ that induce an internal conflict share an edge with a common triangle $\triangle$ of $G_F$. Since $L_{\triangle }$ is consistent, there exist at most 6 triangles in $L_\triangle$ incident to $\triangle$. Hence, at most $\left( {\begin{array}{c}6\\ 2\end{array}}\right) = 15$ pairs of triangles sharing an edge with $\triangle$ can induce an internal conflict.    $\square$

Extending $\varGamma _F$ to a PR of G. Next, we show how to test whether there is a choice of embeddings for the triangles in $L_\triangle$ that yields a PR of G. We distinguish two cases, based on whether $r\ge 2$ or $r<2$.

In this case there are no flat isosceles triangles, and hence the setting is much simpler than the one depicted in Fig. 6. Every leaf triangle in $L_\triangle$ is a small equilateral triangle whose parent is a tall isosceles triangle. We act as follows. For any two triangles $\triangle _1,\triangle _2 \in L_\triangle$ that share an edge e, we embed $\triangle _1$ and $\triangle _2$ in $\varGamma _F$ on opposite sides of e. We embed every other leaf triangle in $L_\triangle$ inside its parent triangle. At the end of this process we obtain, in linear time, a straight-line realization $\varGamma$ of G, and a plane embedding $\mathcal E$ of G.

Lemma 4

G has a PR if and only if $\varGamma$ is planar.

Proof Sketch

First, if two leaf triangles share an edge e, then they lie on opposite sides of e in any PR, since they would overlap otherwise. Second, each isosceles triangle may contain only one leaf triangle, since it has only one side of length $w_1$. Hence, embedding a leaf triangle $\triangle$ inside an isosceles triangle that shares an edge with $\triangle$ cannot cause crossings, since $\triangle$ does not induce internal conflicts. Therefore, a crossing in $\varGamma$ can only be caused by framework and external conflicts, which are, however, unavoidable.    $\square$

By Lemma 4, in order to test whether G admits a PR, we can apply Theorem 1 to test in O(n) time whether $\varGamma$ is a PR of G with embedding $\mathcal E$.

In this case there might be flat isosceles triangles in G which might or might not need to be embedded inside a framework triangle; in Fig. 6 such triangles are shaded light gray. Also, more than one leaf triangle can be drawn inside the same framework triangle which might or might not induce internal conflicts. Recall that the triangles in $L_{\triangle }$ are small equilateral triangles and/or flat isosceles triangles.

We construct a 2SAT formula $\phi$ with a Boolean variable for each triangle $\triangle \in L_\triangle$. The values of $\phi$ are associated with the two possible embeddings of $\triangle$. If two triangles in $L_\triangle$ induce a conflict for certain embeddings, then $\phi$ contains a clause that is True if and only if, at least one of the variables representing the triangles does not have the value corresponding to the embedding generating the conflict. Further, for each triangle that induces a framework conflict, $\phi$ contains a clause that is True if and only if, the variable representing the triangle does not have the value corresponding to an outer embedding. We test in $O(|\phi |)$ time if $\phi$ is satisfiable [6]. In the positive case, we obtain a PR of G from $\varGamma _F$ by embedding each triangle in $L_\triangle$ according to the value of the corresponding variable. We reject the instance in the negative case.

It only remains to prove that the number of conflicts (and hence the size of $\phi$) is in O(n) and that such conflicts can be found in O(n) time. Detecting internal conflicts is fairly easy: i. by Lemma 1, triangles inducing an internal conflict are “close” in T (they share an edge with a common framework triangle); ii. by Lemma 3, there exist O(1) leaf triangles sharing an edge with the same framework triangle; and iii. since $L_{\triangle }$ is consistent, the maximum degree of T is bounded by a constant.

Hence, by traversing T we compute in O(n) time the set of O(n) pairs of leaf triangles that induce an internal conflict.

Efficiently detecting external and framework conflicts is more challenging. Let $L^\prime _{\triangle }$ be the subset of $L_\triangle$ composed of those triangles that are incident to external edges of $\varGamma _F$. We give an outer embedding to every triangle in $L^\prime _{\triangle }$. This results in a (possibly non-planar) straight-line realization $\varGamma ^\prime _F$ of the graph $G^\prime _F:=G_F \cup L^\prime _{\triangle }$. We now construct a bounded-degree graph H whose nodes are associated with sets of vertices of $G^\prime _F$ so that the following properties hold: (a) Each node is associated with O(1) degree-2 vertices of G that belong to triangles in $L^\prime _{\triangle }$, (b) if two triangles in $L^\prime _\triangle$ induce an external conflict, then their degree-2 vertices are associated either with the same node or with adjacent nodes, and (c) if a triangle $\triangle \in L^\prime _\triangle$ intersects an edge e of $G_F$ (inducing a framework conflict), then the degree-2 vertex of $\triangle$ and the end-vertices of e are associated either with the same node or with adjacent nodes.

After constructing H, the external and framework conflicts can be detected with a linear-time traversal of H.

Fig. 7.

The straight-line realization $\varGamma ^\prime _F$ of the graph $G^\prime _F:=G_F \cup L^\prime _{\triangle }$, where each triangle in $L'_\triangle$ has an outer embedding. The triangles of $G_F$ are gray and those in $L^\prime _\triangle$ are white. The leaf triangles in the dashed cell can induce conflicts only with the triangles in the eight highlighted cells surrounding such a cell.

The graph H is defined as follows. Assume that the bottom-left corner of the bounding box of $\varGamma ^\prime _F$ lies on the origin of the Cartesian axes. Consider a square grid covering the plane whose grid cells have side length $3w_2$; see Fig. 7. Assign a label $l(v) = (\lfloor \frac{x(v)}{3w_2}\rfloor , \lfloor \frac{y(v)}{3w_2}\rfloor )$ to each vertex v of $G'_F$. Then H has a node for each label assigned to at least one vertex of $G'_F$, and two distinct nodes (i, j) and $(i^\prime ,j^\prime )$ are connected if and only if $\vert i-i' \vert \le 1$ and $\vert j-j' \vert \le 1$. Note that H has O(n) edges since it has at most n nodes and maximum degree 8.

We now prove that H satisfies Property (a). The number of degree-2 vertices of G that belong to triangles in $L^\prime _\triangle$ and are associated with a node (i, j) of H, is upper bounded by the number k of framework triangles that i. are contained in the union of the grid cell (i, j) and its 8 surrounding grid cells, and ii. share an edge with a triangle in $L^\prime _\triangle$. Note that k is actually the number of big equilateral and tall isosceles triangles in such nine cells. Since the area of a big equilateral or tall isosceles triangle is at least the area of a small equilateral triangle, then k is upper bounded by the ratio between the area of 9 cells, which is $81w_2^2$, and the area of a small equilateral triangle, which is $w_1^2\sqrt{3}/4$. Therefore, since $r < 2$, we have that $k \in O(r^2) \subseteq O(1)$.

We next sketch an algorithm to construct H in O(n) time. The vertex set of H is constructed by removing repetitions from the set of labels l(v) computed for the vertices v in $G'_F$. To this aim, we compute a total order $\pi$ of the vertices of $G'_F$ such that, for any two vertices u and v with $l(u)=(i_u,j_u)$ and $l(v)=(i_v,j_v)$, we have $u\prec _{\pi } v$ if and only if i. $i_u < i_v$ or ii. $i_u = i_v$ and $j_u < j_v$.

Since $G'_F$ is connected and any edge of $G'_F$ has length at most $w_2$, then $0 \le i,j \le \frac{w_2 n}{3w_2} = \frac{1}{3} n$ for any label (i, j). Hence, we compute $\pi$ in O(n) time with counting sort. Since vertices with the same label are consecutive in $\pi$, repetitions can be removed with a linear scan of $\pi$.

Fig. 8.

The edge set of the graph H computed from the drawing $\varGamma ^\prime _F$ in Fig. 7. The sets $E_{-}, E_{|}, E_{/}$, and $E_{\backslash }$ are shown in yellow, blue, green, and red, respectively (Color figure online).

The edge set of H consists of four disjoint subsets $E_{-}$, $E_{|}$, $E_{/}$, and $E_{\backslash }$. These sets contain the edges that connect nodes of H corresponding to grid cells that are adjacent horizontally, vertically, along the main, and the minor diagonal, respectively; see Fig. 8. We appropriately define four orders $\pi _{-}$, $\pi _{|}$, $\pi _{/}$, and $\pi _{\backslash }$ of the nodes of H such that nodes that are connected by an edge in $E_{-}$, $E_{|}$, $E_{/}$, and $E_{\backslash }$ are consecutive in the corresponding order. We compute the four sets of edges with a linear scan of the orders $\pi _{-}$, $\pi _{|}$, $\pi _{/}$, and $\pi _{\backslash }$.

4 Maximal Outerplanar Graphs

In this section we study the FEPR problem for weighted outerplanar 2-trees, i.e., for weighted maximal outerplanar graphs. We prove the following theorems.

Theorem 5

Let G be an n-vertex weighted maximal outerpath. There is an O(n)-time algorithm to test whether G admits a PR and to construct one, if any.

Theorem 6

Let G be an n-vertex weighted maximal outerpillar. There is an $O(n^3)$-time algorithm to test whether G admits a PR and to construct one, if any.

Let G be a weighted 2-tree and e be an edge of G. An of G is a PR of G such that e is incident to the outer face. An e-outer realization $\varGamma$ of G is if, for every e-outer realization $\varGamma '$ of G, there is a rigid transformation of $\varGamma$ such that the segment representing e coincides with the one in $\varGamma '$ and such that the interior of $\varGamma$ is a subset of the interior of $\varGamma '$.

Fig. 9.

A maximal outerpath G.

We sketch the proof of Theorem 5; the proof of Theorem 6 uses similar ideas. Let G be an n-vertex weighted maximal outerpath; see Fig. 9. Let T be the dual tree of the outerplane embedding $\mathcal O$ of G; since G is an outerpath, T is a path $(p_1,\dots ,p_k)$. For $i=1,\dots ,k$, let $c_i$ be the 3-cycle of G bounding the internal face of $\mathcal O$ dual to $p_i$ and let $\mathcal C_i$ be the unique, up to rigid transformation, PR of $c_i$. For $i=1,\dots ,k-1$, let $e_i$ be the edge of G dual to $(p_i,p_{i+1})$. Let $x\in \{1,\dots ,k\}$ be such that $c_{x}$ has maximum edge length sum. Let $G_1$ and $G_2$ be the subgraphs of G composed of the cycles $c_1,c_2,\dots ,c_{x-1}$ and $c_{x+1},c_{x+2},\dots ,c_k$, respectively. Since the length of $c_{x}$ is maximum, the restrictions of any PR of G to $G_1$ and $G_2$ are $e_{x-1}$-outer and $e_{x}$-outer realizations, respectively. We prove that $G_1$ (resp. $G_2$) admits an $e_{x-1}$-outer (resp. $e_x$-outer) realization if and only if it admits an $e_{x-1}$-optimal (resp. $e_x$-optimal) realization. The core of the proof of Theorem 5 is an O(n)-time algorithm, called Outer-Checker, that constructs an $e_{x-1}$-optimal (resp. an $e_x$-optimal) realization $\varGamma _1$ of $G_1$ (resp. $\varGamma _2$ of $G_2$) and its plane embedding, if any such a realization exists. If Outer-Checker concludes that both $G_1$ and $G_2$ admit a PR, then $\varGamma _1$ and $\varGamma _2$ (as well as their embeddings) can be combined in four ways with $\mathcal C_x$ (see Fig. 10) and each resulting straight-line realization can be tested for planarity in O(n) time, by Theorem 1.

Fig. 10.

The four different ways to combine $\varGamma _1$ and $\varGamma _2$ with $\mathcal C_x$.

We describe how Outer-Checker works on $G_1$. A key observation is that the restriction of any $e_{x-1}$-optimal realization of $G_1$ to the graph $G^i_1$ composed of the cycles $c_1,c_2,\dots ,c_i$ is an $e_i$-optimal realization of $G^i_1$. This allows Outer-Checker to work by induction on i to decide whether $G^i_1$ has an $e_i$-optimal realization $\varGamma ^i_1$. If $i=1$, the graph $G^1_1$ is the cycle $c_1$ whose unique PR $\mathcal C_1$ is $e_1$-optimal. If $i>1$, an $e_i$-optimal realization $\varGamma ^i_1$ of $G^i_1$ is constructed, if it exists, by combining $\varGamma ^{i-1}_1$ and $\mathcal C_i$ so that $e_{i-1}$ coincides in the two realizations. Three things might happen. First, if $\varGamma ^{i-1}_1$ “fits” inside $\mathcal C_i$, as in Fig. 11(left), then the resulting PR $\varGamma ^i_1$ is $e_i$-optimal. Else, if $\varGamma ^{i-1}_1$ “fits” outside $\mathcal C_i$, as in Fig. 11(middle), once cycles $\mathcal C_i$ and $\mathcal C_{i-1}$ lie on different sides of $e_{i-1}$, then the resulting PR $\varGamma ^i_1$ is $e_i$-optimal. Otherwise, $G^i_1$ admits no $e_i$-optimal realization, as in Fig. 11(right).

A naive implementation of Outer-Checker takes $O(n^2)$ time. Indeed, for each of the O(n) inductive steps, one can check in O(n) time whether $\varGamma ^{i-1}_1$ fits inside and/or outside $\mathcal C_i$ using Theorem 1. We achieve O(n) total running time avoiding a planarity test at each step. For $i=1,\dots ,x-1$, we compute a “candidate” straight-line realization $\varGamma ^i_1$ of $G^i_1$, and only test for planarity the final realization $\varGamma ^{x-1}_1$. By “candidate” we mean that, if $G^i_1$ admits an $e_i$-optimal realization, then $\varGamma ^i_1$ is such a realization. In order to do that, Outer-Checker dynamically maintains the boundary $\mathcal B^i_1$ of the convex hull of $\varGamma ^i_1$, which is guaranteed to actually be the boundary of the convex hull of $\varGamma ^i_1$ if $\varGamma ^i_1$ is planar. We compute $\mathcal B^i_1$ by suitably exploiting a linear-time algorithm by Melkman [35], which incrementally computes the convex hull of a point set spanned by a planar path, provided that the points are given in the order of the path.

Fig. 11.

The three cases in the construction of $\varGamma ^i_1$. The triangle $\mathcal C_i$ is bold. (Left) $\varGamma ^{i-1}_1$ fits inside $\mathcal C_i$. (Middle) $\varGamma ^{i-1}_1$ does not fit inside $\mathcal C_i$, but it fits outside $\mathcal C_i$. (Right) $\varGamma ^{i-1}_1$ fits neither inside nor outside $\mathcal C_i$.

After constructing $\varGamma ^{x-1}_1$ (which comes with a plane embedding), we test its planarity in O(n) time using Theorem 1. If the test is successful, $\varGamma ^{x-1}_1$ is an $e_{x-1}$-optimal PR of $G^{x-1}_1$, otherwise no $e_{x-1}$-optimal PR of $G^{x-1}_1$ exists. Each step of Outer-Checker takes O(1) time, except for the computation of the boundary $\mathcal B^i_1$. However, the computation of the boundaries $\mathcal B^{1}_1,\mathcal B^{2}_1,\dots ,\mathcal B^{x-1}_1$ takes O(n) time in total [35]. Hence, the overall running time of Outer-Checker is in O(n).

5 2-Trees with Short Longest Path

In this section, we sketch a proof of the following theorem.

Theorem 7

Let G be an n-vertex weighted 2-tree and let $\ell$ be the length of a longest path of G. There is an $n^{O(4^{\ell })}$-time algorithm to test whether G admits a PR and to construct one, if any.

Theorem 7 is actually a corollary of a stronger theorem, which relates to SPQ-trees; these are a specialization for 2-trees of the well-known  [22, 29]. The $\mathcal T$ of G is a tree that represents a recursive decomposition of G into subgraphs along separation pairs. Each node $\mu$ of $\mathcal T$ corresponds to a subgraph $G_{\mu }$ of G, which is joined to the rest of the graph via two vertices $u_\mu$ and $v_{\mu }$. Assume that $\mathcal T$ is rooted at the neighbor of an edge of G with maximum length and let h be the height of $\mathcal T$. We design an $n^{O(2^{h})}$-time algorithm that tests whether G admits a PR and, in the positive case, constructs such a realization. Then Theorem 7 follows, as we can prove that $h\le 2\ell -2$.

The $n^{O(2^{h})}$-time algorithm performs a visit of $\mathcal T$. When visiting a node $\mu$, the algorithm either concludes that G admits no PR, or constructs a set $\mathcal R_{\mu }$ of “optimal” PRs of $G_{\mu }$. Here, “optimal” means that, for every PR $\varGamma _{\mu }$ of $G_{\mu }$, there is a PR $\varGamma '_{\mu }\in \mathcal R_{\mu }$ whose interior is a subset of the interior of $\varGamma _{\mu }$, after a suitable rigid transformation. The main ingredient needed for bounding the running time of the algorithm is the following. Suppose that $G_{\mu }$ consists of a “parallel” composition of graphs $G_{\nu _1},\dots ,G_{\nu _k}$. Then “few” of the permutations of $G_{\nu _1},\dots ,G_{\nu _k}$ need to be considered when constructing $\mathcal R_{\mu }$. Namely, we can sort $G_{\nu _1},\dots ,G_{\nu _k}$ by increasing length of the 2-edge paths between $u_{\mu }$ and $v_{\mu }$ they contain. Then, in any PR of G, the graph $G_{\nu _i}$ is either “to the left” or “to the right” of all the graphs $G_{\nu _1},\dots ,G_{\nu _{i-1}}$; further, whether a PR of G is optimal only depends on the choice of the “leftmost” and “rightmost” graphs among $G_{\nu _1},\dots ,G_{\nu _k}$ (and on their drawings, which are taken from $\mathcal R_{\nu _1},\dots ,\mathcal R_{\nu _k}$), and not on the permutation of the remaining graphs, as long as planarity is ensured.

6 Open Problems

Our results on the FEPR problem when G is a 2-tree motivate the study of several open questions:

• Determine the computational complexity of the FEPR problem for weighted 2-trees with 3 prescribed edge lengths (we proved it is linear-time solvable for 2 and -hard for 4).

• Determine if it is possible to improve our  algorithm for general 2-trees to an  algorithm.

• Study the computational complexity of the FEPR problem for general maximal outerplanar graphs.

• Study the computational complexity of the FEPR problem for graphs with treewidth 2 and for 2-degenerate planar graphs; both these classes generalize the one of 2-trees.