On the Edge-Length Ratio of 2-Trees

Abstract

We study planar straight-line drawings of graphs that minimize the ratio between the length of the longest and the shortest edge. We answer a question of Lazard et al. [Theor. Comput. Sci. 770 (2019), 88–94] and, for any given constant r, we provide a 2-tree which does not admit a planar straight-line drawing with a ratio bounded by r. When the ratio is restricted to adjacent edges only, we prove that any 2-tree admits a planar straight-line drawing whose edge-length ratio is at most $4 + \varepsilon$ for any arbitrarily small $\varepsilon > 0$, hence the upper bound on the local edge-length ratio of partial 2-trees is 4.

The research was initiated during workshop Homonolo 2018. Research partially supported by MIUR, the Italian Ministry of Education, University and Research, under Grant 20174LF3T8 AHeAD: efficient Algorithms for HArnessing networked Data. V. Blažej acknowledges the support of the OP VVV MEYS funded project CZ.02.1.01/0.0/0.0/16_019/0000765 “Research Center for Informatics”. This work was supported by the Grant Agency of the Czech Technical University in Prague, grant No. SGS20/208/OHK3/3T/18. The work of J. Fiala was supported by the grant 19-17314J of the GA ČR.

1 Introduction

Straight-line drawings of planar graphs are thoroughly studied both for their theoretical interest and their applications in a variety of disciplines (see, e.g., [6, 12]). Different quality measures for planar straight-line drawings have been considered in the literature, including area, angular resolution, slope number, average edge length, and total edge length (see, e.g., [8, 9, 11]).

This paper studies the problem of computing planar straight-line drawings of graphs where the length ratio of the longest to the shortest edge is as small as possible. We recall that the problem of deciding whether a graph admits a planar straight-line drawing with specified edge lengths is NP-complete even when restricted to 3-connected planar graphs [7] and the completeness persists in the case when all given lengths are equal [4]. In addition, deciding whether a degree-4 tree has a planar drawing such that all edges have the same length and the vertices are at integer grid points is NP-complete [1].

In the attempt of relaxing the edge length conditions which make the problem hard, Hoffmann et al. [9] propose to minimize the ratio between the longest and the shortest edges among all straight-line drawings of a graph. While the problem remains hard for general graphs (through approximation of unit disk graphs [5]), Lazard et al. prove [10] that any outerplanar graph admits a planar straight-line drawing such that the length ratio of the longest to the shortest edges is strictly less than 2. This result is tight in the sense that for any $\varepsilon >0$ there are outerplanar graphs that cannot be drawn with an edge-length ratio smaller than $2-\varepsilon$. Lazard et al. also ask whether their construction could be extended to the class of series-parallel graphs.

We answer this question in the negative sense, by showing that a subclass of series-parallel graphs, called 2-trees, does not allow any planar straight-line drawing of bounded edge-length ratio. In fact, a corollary of our main result is the existence of an $\varOmega (\log n)$ lower bound for the edge-length ratio of planar straight-line drawings of n-vertex 2-trees. Motivated by this negative result, we consider a local measure of edge-length ratio and prove that when the ratio is restricted only to the adjacent edges, any series-parallel graph admits a planar straight-line drawing with local edge-length ratio at most $4 + \varepsilon$, for any arbitrarily small $\varepsilon >0$. The proof of this upper bound is constructive, and it gives rise to a linear-time algorithm assuming a real RAM model of computation.

It is worth noticing that Borrazzo and Frati have shown that any 2-tree on n vertices can be drawn with edge-length ratio $O(n^{0.695})$ [3]. This, together with our $\varOmega (\log n)$ result, defines a non-trivial gap between the upper and lower bound on the edge-length ratio of planar straight-line drawings of partial 2-trees. We recall that Borrazzo and Frati also show an $\varOmega (n)$ lower bound on the edge-length ratio of general planar graphs [3].

The rest of the paper is organized as follows. Preliminaries are in Sect. 2; the $\varOmega (\log n)$ lower bound is proved in Sect. 3; Sect. 4 presents a constructive argument for an upper bound on the local edge-length ratio of partial 2-trees. Conclusions and open problems can be found in Sect. 5. Omitted proof can be found in the appendix of the full version of the paper which is available online [2].

2 Preliminaries

We use capital letters $A,B,\dots$, for the points in the Euclidean plane. For points A and B, let |AB| denote the Euclidean distance between A and B. The symbol $\bigtriangleup ABC$ denotes the triangle determined by three distinct non-colinear points A, B, and C. The symbol $\angle BAC$ stands for the angle at vertex A of the triangle $\bigtriangleup ABC$.

For a polygon Q, we denote its perimeter by P(Q) and its area by A(Q).

We consider finite nonempty planar graphs and their planar straight-line drawings. Once a straight-line drawing of a graph G is given, with a slight abuse of notation we use the same symbol for a vertex U and the point U representing the vertex U in the drawing; the same symbol UV for an edge and the corresponding segment; as well as $\bigtriangleup UVW$ for an induced cycle of length three and the corresponding triangle.

When we consider graphs as combinatorial objects, we often use lowercase symbols u or e for the vertices and edges.

The edge-length ratio of a planar straight-line drawing of a graph G is the ratio between the length of the longest and the shortest edge of the drawing.

Definition 1

The edge-length ratio $\rho (G)$ of a planar graph G is the infimum edge-length ratio taken over all planar straight-line drawings of G.

The class of 2-trees is defined recursively: an edge is a 2-tree. If e is an edge of a 2-tree, then the graph, formed by adding a new vertex u adjacent to both endpoints of e, is also a 2-tree. In such a situation we say that u has been added as a simplicial vertex to e. A partial 2-tree is a subgraph of a 2-tree.

3 Edge-Length Ratio of 2-Trees

We recall that 2-trees are planar graphs. The main result of this section is the following.

Theorem 1

For any $r \ge 1$, there exists a 2-tree G with edge-length ratio $\rho (G) \ge r$.

To prove Theorem 1, for a given r we argue that a sufficiently large 2-tree, drawn with the longest edge having length r, contains a triangle with area at most $\frac{1}{4}$ (Corollary 1). Then, inside this triangle of small area we build a sequence of triangles with perimeters decreasing by at least 1 at every two steps (Lemmas 5 and 6), which results in a triangle with an edge of length less than 1.

We consider a special subclass $\mathcal {G}=\{G_0,G_1,\dots \}$ of 2-trees with labeled vertices and edges constructed as follows: $G_0$ is the complete graph $K_3$ whose vertices and edges are given the label 0. The graph $G_{i+1}$ is obtained by adding five simplicial vertices to each edge of label i of $G_i$. Each newly created vertex and edge gets label $i+1$. See Fig. 1 for an example where the black vertices and edges have label 0, the blue ones have label 1, and the red ones have label 2.

Fig. 1.

The 2-trees $G_1$ and $G_2$. Black color corresponds to label 0, blue to 1, and red to 2. Separating triangle $\varDelta _1$ is emphasized by a dashed line in $G_1$. (Color figure online)

A separating triangle of level i in a straight-line drawing of a 2-tree G is an unordered triple $\{U,V,W\}$ of mutually adjacent vertices such that the vertex W of label i was added as a simplicial vertex to the edge UV in the recursive construction of G and the triangle $\bigtriangleup UVW$ contains in its interior at least two other vertices with label i which are simplicial to the edge UV. For example, in Fig. 1a) vertices $\{U,V,W\}$ form a separating triangle of level 1.

Lemma 1

For any $k> i\ge 1$, for any planar straight-line drawing of the graph $G_k$, and for any edge e of $G_k$ labeled by i, there exists a separating triangle of level $i+1$ containing the endpoints of e.

Proof

If a common edge of two triangles is traversed in the same direction when following their boundaries in the clockwise manner, then these triangles are nested, i.e. the interior of one contains the other one. Since we have five vertices simplicial to e, out of the corresponding five triangles in at least three e traversed in the same direction when following their boundaries in the clockwise manner. Thus at least three triangles are nested and the outermost of these is the desired separating triangle.

(For the clarity of presentation we have assumed a straight-line drawing, where the graph-theoretic term triangle coincides with the geometric one. This assumption could indeed be neglected when we consider a triangle in a planar drawing as the Jordan curve formed from the drawing of a 3-cycle.)

We proceed to show that any drawing of $G_k$ contains a triangle of sufficiently small area. To this aim, we construct a sequence of nested triangles such that each triangle’s area is half of the previous triangle’s area. We denote as $\varDelta _i$ a separating triangle of level i in an embedding of $G_k$, where $i \le k$.

Lemma 2

For any $k\ge 1$, any planar straight-line drawing of $G_k$ contains a sequence of triangles $\varDelta _1, \varDelta _2, \dots , \varDelta _{k}$, where for any $i\in \{1,\dots ,k\}$ the triangle $\varDelta _{i}$ is a separating triangle of level i, and for each $i>1$, in addition, $\varDelta _{i}$ is in the interior of $\varDelta _{i-1}$ and $A(\varDelta _{i}) \le \frac{1}{2} A(\varDelta _{i-1})$.

Proof

We prove the lemma by induction on i. For $i=1$ we apply Lemma 1 on any edge e of label 0 in $G_k$ to get the triangle $\varDelta _1$.

When $i\in \{2,\dots ,k\}$, we assume by inductive hypothesis that the graph $G_k$ contains a sequence of triangles $\varDelta _1, \varDelta _2, \dots , \varDelta _{i-1}$ satisfying the constraints. Let U be one of the two vertices of label $i-1$ in the interior of $\varDelta _{i-1}$ and let e and f be the two edges of label $i-1$ incident to U.

We apply Lemma 1 on both of e and f to obtain two separating triangles of level i inside $\varDelta _{i-1}$, see Fig. 2. Since the drawing was planar, the two triangles are non-overlapping. We choose the triangle with the smaller area to be $\varDelta _i$ to assure that $A(\varDelta _i) \le \frac{1}{2} A(\varDelta _{i-1})$.

Fig. 2.

Two separating triangles created in the interior of $\varDelta _{i-1}$

Corollary 1

For any $r > 1$ and $k \ge 2+ 2 \log _2 r$, every planar straight-line drawing of $G_k$ with edge lengths at most r contains a separating triangle of area at most $\frac{1}{4}$.

Proof

If all edges have length at most r, the area of $\varDelta _1$ is bounded by $\frac{\sqrt{3}}{4}r^2$. By Lemma 2, any drawing of $G_k$ contains a sequence of nested separating triangles whose last element $\varDelta _k$ has area at most $\frac{1}{2^{k-1}} \frac{\sqrt{3} r^2}{4}\le \frac{1}{4}$.

Before we proceed to the next step in our construction, we need some elementary facts from the trigonometry.

We call thin any triangle with edges of length at least 1 and area at most $\frac{1}{4}$. Any thin triangle has height at most $\frac{1}{2}$ and hence it has one obtuse angle of size at least $\frac{2\pi }{3}$ and two acute angles, each of size at most $\frac{\pi }{6}$.

Lemma 3

Let $\bigtriangleup ABC$ be a thin triangle, where the longest edge is AB and let $D\in \bigtriangleup ABC$ be such that $|CD|\ge 1$. Then one of the angles $\angle ACD$ or $\angle BCD$ is obtuse.

Proof

Assume by contradiction that both $\angle ACD$ and $\angle BCD$ are acute. Without loss of generality we may also assume that $\angle ACD \ge \angle BCD$. Since $\angle ACD + \angle BCD = \angle ACB \ge \frac{2\pi }{3}$, it follows that $\angle ACD \ge \frac{\pi }{3}$.

Fig. 3.

To the argument that $\angle ACD$ cannot be acute.

Then the triangle $\bigtriangleup ACD$ has height at least $\frac{\sqrt{3}}{2}$, see Fig. 3. Thus it has area at least $\frac{\sqrt{3}}{4}$, a contradiction with the fact that the surrounding thin triangle $\bigtriangleup ABC$ has area at most $\frac{1}{4}$.

Now we focus our attention on the perimeters of the considered triangles.

Lemma 4

Let $\bigtriangleup ABC$ be a thin triangle, where the longest edge is AB. Denote by Q the polygon, created by cutting off an isosceles triangle $\bigtriangleup BDE$ with both edges BD and BE of length 1. Then the perimeter of any triangle located in the polygon Q is at most $P(\bigtriangleup ABC)-1$.

Fig. 4.

Cutting-off the triangle $\bigtriangleup BDE$.

See Fig. 4 for an example of cutting off an isosceles triangle.

Proof

Assume for a contradiction that some triangle T has perimeter $P(T)> P(\bigtriangleup ABC)-1$. Since T and Q are nested convex objects, we have that that $P(Q) \ge P(T) > P(\bigtriangleup ABC)-1$. Then the length of the edge DE is greater than 1 and hence the angle $\angle DBE \ge \frac{\pi }{3}$, a contradiction with the property that the acute angles of a thin triangle are at most $\frac{\pi }{6}$.

We now return to our construction and show that a separating triangle with a small area is guaranteed to contain a separating triangle of a significantly smaller perimeter. In the following two lemmas we distinguish two complementary cases, namely whether the edge of level $i-1$ of a separating triangle of level i is incident to its obtuse angle or not.

Lemma 5

Let $G_k$ have a planar straight-line drawing with edge lengths at least 1 and let $\bigtriangleup UVW$ be a thin separating triangle of level i, where $i\le k-1$. Assume that the edge UV is of level $i-1$ and that it is incident to the obtuse angle of $\bigtriangleup UVW$. Then $\bigtriangleup UVW$ contains a thin separating triangle T of level $i+1$ whose perimeter satisfies $P(T) \le P(\bigtriangleup UVW)-1$.

Fig. 5.

Case analysis for Lemma 5.

Proof

Let X and Y be the two vertices of level i simplicial to the edge UV inside the triangle $\bigtriangleup UVW$. As the embedding of $G_k$ is non-crossing straight-line, we may assume without loss of generality that the vertex X is inside $\bigtriangleup UVY$.

As all triangles in our further consideration are inside the thin triangle $\bigtriangleup UVW$, they have area at most $\frac{1}{4}$. By the definition of thin triangle they are also thin, as otherwise we would get in $G_k$ an edge shorter than 1, which violates the assumptions of the Lemma. We distinguish several cases depending on the position of the obtuse angle of the considered triangles, see Fig. 5.

• a) The obtuse angle of $\bigtriangleup UVX$ is at V. By Lemma 1 we find a separating triangle T incident with the edge VY. Since T takes place within the angle $\angle WVX$, it is at distance at least 1 from U. Hence we may apply Lemma 4 to cut away the isosceles triangle in the neighborhood of vertex U, to argue that the perimeter of T is at most $P(\bigtriangleup UVW)-1$.

• b) The obtuse angle of $\bigtriangleup UVX$ is at X and the separating triangle $\bigtriangleup VXZ$ incident with VX obtained by by Lemma 1 is inside $\bigtriangleup UVX$. As $\bigtriangleup UXV$ is thin, we get that $\angle WVX \ge \frac{\pi }{2}$. Hence all points of $\bigtriangleup VXZ$ are at distance at least 1 from W. We cut away the vertex W and obtain $P(\bigtriangleup VXZ)\le P(\bigtriangleup UVW)-1$.

• c) The angle $\angle UXV$ is obtuse, the separating triangle $\bigtriangleup VXZ$ is outside $\bigtriangleup UVX$ and the angle $\angle VXZ$ is obtuse. We apply Lemma 3 to get that $\angle WVZ$ is obtuse—the case of $\angle UVZ$ being obtuse is excluded as this angle is composed from acute angles of two thin triangles: $\bigtriangleup UVX$ and $\bigtriangleup VXZ$. Then we cut away the vertex W as in the previous case and obtain the claimed result.

• d) The angle $\angle UXV$ is obtuse, the separating triangle $\bigtriangleup VXZ$ is outside $\bigtriangleup UVX$ and the angle $\angle VXZ$ is acute. Now cut away the vertex U (as $|UX|\ge 1$), and get $P(\bigtriangleup VXZ)\le P(\bigtriangleup UVW)-1$.

Note that only when Case a) occurred, we used the existence of two vertices of label i within the separating triangle $\bigtriangleup UVW$. If Y was not present, we would have to discuss the case that the obtuse angle of $\bigtriangleup UVX$ is at V and both separating triangles of level $i+1$ are inside $\bigtriangleup UVX$. For such a case it is possible to find a configuration where Lemma 4 cannot be immediately applied, see Fig. 6.

Fig. 6.

The case that avoids cutting. Note that X could be arbitrary close to W and Z to U.

Lemma 6

Let $G_k$ have a planar straight-line drawing with edge length at least 1 and let $\bigtriangleup UVW$ be a thin separating triangle of level $i\le k-2$. Assume that the edge UV is of level $i-1$ and that it is not incident to the obtuse angle of $\bigtriangleup UVW$. Then $\bigtriangleup UVW$ contains a thin separating triangle T of level at most $i+2$ whose perimeter satisfies $P(T) \le P(\bigtriangleup UVW)-1$.

Fig. 7.

Case analysis for Lemma 6.

Proof

Similarly to the previous lemma, let X be one of the two vertices of level i simplicial to the edge UV inside the triangle $\bigtriangleup UVW$, see Fig. 7. By Lemma 1 we construct a separating triangle $\bigtriangleup UXZ$ incident with the edge UX.

• a) If the angle $\angle UXZ$ is acute, then we cut away V and apply Lemma 4 to obtain $P(\bigtriangleup UXZ) \le P(\bigtriangleup UVW)-1$.

• b) If the angle $\angle UXZ$ is obtuse, then we apply Lemma 5 for the triangle $\bigtriangleup UXZ$ to find a suitable separating triangle T of level $i+2$ within $\bigtriangleup UXZ$.

Corollary 2

For any $r > 1$, $k\ge 1$, $l\ge 0$ and any planar straight-line drawing of $G_{k+l}$ with edge length at least 1 it holds: If the drawing contains a thin separating triangle of level $k\ge 1$, then it has a triangle of perimeter at most $2r+\frac{1}{4}-\lfloor \frac{l}{2} \rfloor$.

Proof

Denote by $\varDelta _0$ the thin triangle of level k in the drawing of $G_{k+l}$. Since all edges have length at most r, any thin triangle it could be drawn inside a rectangle $r\times \frac{1}{8}$, hence it has perimeter at most $2r+\frac{1}{4}$.

We involve Lemmas 5 and 6, to find in the drawing of $G_{k+l}$ a sequence of nested separating triangles of length at least $l+1$ with decreasing perimeters.

We argue that the sequence can be chosen such that for any $i\in \{1,2,\dots ,\lfloor \frac{l}{2} \rfloor \}: P(\varDelta _{2i})\le P(\varDelta _{2i-2})-1 \le P(\varDelta _0)-i$. We distinguish two cases whether the edge of level $2i-3$ in $\varDelta _{2i-2}$ is incident to the obtuse angle of $\varDelta _{2i-2}$ or not:

• In the first case we apply Lemma 5 to get $P(\varDelta _{2i-1})\le P(\varDelta _{2i-2})-1$. As $\varDelta _{2i}$ is inside $\varDelta _{2i-1}$, we get $P(\varDelta _{2i})\le P(\varDelta _{2i-2})-1$.

• Otherwise we apply Lemma 6 to derive $P(\varDelta _{2i})\le P(\varDelta _{2i-2})-1$ directly.

Now we combine the two parts together to prove Theorem 1.

Proof

(of Theorem 1). For given r we choose $k = \lceil 2+ 2 \log _2 r \rceil$ and consider the graph $G_{k+4r}$. Assume for a contradiction that $G_{k+4r}$ allows a drawing of edge-length ratio at most r. Up to an appropriate scaling, we assume that the longest edge of such drawing has length r and hence the shortest has length at least 1.

In the drawing of the graph $G_{k+4r}$ consider a sequence of separating triangles $\varDelta _1,\dots ,\varDelta _{k+4r}$ where $\varDelta _1,\dots ,\varDelta _k$ are chosen as shown in Corollary 1.

By Corollary 1, the triangle $\varDelta _k$ is thin, so we can extend the sequence with $\varDelta _k,\dots ,\varDelta _{k+4r}$ according to Corollary 2.

By Corollary 2, $P(\varDelta _{k+4r})\le 2r+\frac{1}{4} -2r = \frac{1}{4}$, a contradiction to the assumption that all triangles of $G_{k+4r}$ have sides of length at least one.

Note that the graph $G_{k+4r}$ has $O^*\big ((10^4)^r\big )$ vertices and edges, as in each iteration we add 10 edges of level i per every edge of level $i-1$. The dependency between the edge-length ratio and the number of vertices could be rephrased as follows:

Corollary 3

The edge-length ratio over the class of n-vertex 2-trees is $\varOmega (\log n)$.

We recall that Borrazzo and Frati prove that every partial 2-tree with n vertices admits a planar straight-line drawing whose edge-length ratio is in $O(n^{0.695})$ [3, Corollary 1].

4 Local Edge-Length Ratio of 2-Trees

The aesthetic criterion studied in the previous section took into account any pair of edges. By our construction of nested triangles, it might happen that two edges attaining the maximum length ratio are far in the graph distance (in the Euclidean distance they are close as the triangles are nested). This observation leads us to the question, whether 2-trees allow drawings where the length ratio of any two adjacent edges could be bounded by a constant. For this purpose we define the local variant of the edge-length ratio as follows:

The local edge-length ratio of a planar straight-line drawing of a graph G is the maximum ratio between the lengths of two adjacent edges (sharing a common vertex) of the drawing.

Definition 2

The local edge-length ratio $\rho _l(G)$ of a planar graph G is the infimum local edge-length ratio taken over all planar straight-line drawings of G.

$$ \rho _l(G) = \inf _{\textit{drawing of }G} \quad \max _{UV,VW\in E_G} \frac{|UV|}{|VW|} $$

Observe that the local edge-length ratio $\rho _l(G)$ is by definition bounded by the global edge-length ratio $\rho (G)$. In particular, every outerplanar graph G allows a drawing witnessing $\rho _l(G)\le 2$ [10]. We extend this positive result to the class of all 2-trees with a slightly increased bound on the ratio.

Theorem 2

The local edge-length ratio of any n-vertex 2-tree G is $\rho _l(G)\le 4$. Also, for any arbitrarily small positive constant $\varepsilon$, a planar straight-line drawing of G with local edge-length ratio at most $4 +\varepsilon$ can be computed in O(n) time assuming the real RAM model of computation.

The proof of Theorem 2 is based on a construction that provides a straight-line drawing of local edge-length ratio $4+\varepsilon$ for any given 2-tree G and any $\varepsilon >0$.

We use a breadth first search (BFS) and and decompose $V_G$ into layers based on the distance from the initial edge e of the recursive definition of the 2-tree. Each such layer $L_i=\{u: \mathrm {dist}(u,e)=i\}$ is a forest, see Fig. 8a).

Fig. 8.

a) A decomposition of a 2-tree G into layers: black $L_0$ (the initial edge), blue $L_1$, red $L_2$, and green $L_3$; b) The tree components of G (Color figure online)

Moreover, for every component C of $L_i, i\ge 1$ we may due to the definition of a 2-tree identify a unique vertex $w\in C$ and two its neighbors $u,v\in L_{i-1}$, as w is the first vertex of C inserted into G, and in the time of its insertion it was simplicial to the edge uv. We call the subgraph of G induced by $C\cup \{u,v\}$ a tree-component rooted in u, v and denote it by $H_{u,v,w}$, see Fig. 8b). Observe that each tree-component of itself is a 2-tree. Moreover the vertices of $H_{u,v,w}$ distinct from u, v and w can be partitioned into two disjoint sets: those adjacent to u and those adjacent to v.

Note that BFS can be executed in O(n) time for a planar graph with n vertices. This procedure can be extended in a straightforward way to determine the tree-components in O(n) time—on each vertex we spend additional constant time to identify the tree component it belongs.

For a line segment AB, let $\overline{AB} = AB\setminus \{A,B\}$ denote for the segment AB without its endpoints.

Definition 3

Let UV be an edge of a planar straight-line drawing of G on at least three vertices. The vacant region for UV is the intersection of all open half-planes determined by all pairs of vertices such that these half-planes contain $\overline{UV}$.

For example, Fig. 9 shows the vacant region for an edge UV in a planar straight-line drawing of a 2-tree. Note that, by the definition, the vacant region for UV is an open convex set with U and V on the boundary.

Fig. 9.

The filled gray region is the vacant region of the edge UV.

We proceed to the main technical step of our construction.

Lemma 7

Let $H_{X,Y,Z}$ be a tree-component of a 2-tree G. For any $\delta >0$, any open convex set S and any two points on the boundary of S, the graph $H_{X,Y,Z}$ can be drawn with the local edge-length ratio at most $2+\delta$ such that vertices X, Y are placed on the chosen two points, the rest of the drawing of $H_{X,Y,Z}$ is inside S, and XY is the longest edge of the drawing.

Fig. 10.

Folding a path in the tree component $H_{X,Y,Z}$. The arrows indicate the vertex movement. (Color figure online)

Instead of the proof of Lemma 7, that is omitted due to space restrictions, we provide a very brief idea of the construction. Observe that in the case that in the case when the tree component $H_{X,Y,Z}$ is a fan centered at X, then it can be folded like an umbrella into the vacant region of XY as depicted in Fig. 10a). In the folded drawing the red edges have the same length upto an additive factor $\delta$, while the blue are twice longer (again upto $+\delta$).

Analogously, if the vertices adjacent to X in $H_{X,Y,Z}$ induce a path and the same for the neighbors of Y, then these two paths can be folded from both sides of XY inside its vacant region, see Fig. 10b). By much more technically involved argument it can be shown that the whole branch of a tree can be folded into the area near the first edge of the branch.

Proof

(of Theorem 2). When $G=K_2$, then it has $\rho _l(K_2)=1$, by Definition 2 (note that U and W need not to be distinct.) Otherwise we proceed by induction on the number of tree components of G.

For any $\varepsilon \in (0,1)$, let $\delta = \frac{\varepsilon }{3}$. The induction hypothesis we aim to prove is:

Claim

Any 2-tree G allows a drawing with local edge-length ratio at most $4+\varepsilon$, where each tree component $H_{X,Y,Z}$ is drawn with local edge length ratio at most $2+\delta$ and XY is the longest edge of the drawing of $H_{X,Y,Z}$.

For the base of the induction G consists of a single tree component $H_{X,Y,Z}$, where XY is the initial edge of construction of G as a 2-tree. We choose any open convex set S and two points X, Y on its boundary and apply Lemma 7.

For the induction step assume that $H_{X,Y,Z}$ is a tree component of G, where Z belongs to the highest possible level. The graph $G'=G\setminus (H_{X,Y,Z}\setminus \{X,Y\})$ (i.e. when we remove from G the component of $L_i$ containing the vertex Z) is a 2-tree, since we may create $G'$ as a 2-tree by the same order of insertions as is used for G, only restricted to the vertices of $G'$. By induction hypothesis $G'$ allows a drawing with local edge-length ratio at most $4+\varepsilon$.

In this drawing we identify the vacant region S for XY and involve Lemma 7 to extend the drawing of $G'$ to the entire G. The only vertices common to $G'$ and $H_{X,Y,Z}$ are X and Y, hence we shall argue that edges incident with X or Y have edge-length ratio at most $4+\varepsilon$, as inside $H_{X,Y,Z}$ the ratio is at most $2+\delta < 4+\varepsilon$ by Lemma 7.

By the construction of the 2-tree, the edge XY may belong to several tree components rooted in X, Y, where it is the longest edge, but only to a single tree-component rotted in the vertices of the preceding level. Consequently, the edge-length ratio of any two edges incident with X or with Y is at most $(2+\delta )^2=4+2\delta +\delta ^2<4+3\delta =4+\varepsilon$.

Finally, we remark that computing the coordinates of the vertices can be executed in constant time per vertex, assuming a real RAM model of computation. It follows that the drawing of G can be computed in O(n) time.

Since any graph of treewidth at most 2, in particular all series-parallel graphs, can be augmented to a 2-tree, Theorem 2 directly implies the following.

Corollary 4

For any graph G of treewidth at most 2, it holds that $\rho _l(G)\le 4$.

5 Conclusions and Open Problems

This paper studied the edge-length ratio of planar straight-line drawing of partial 2-trees. It proved an $\varOmega (\log n)$ lower bound on such edge-length ratio and it proved that every partial 2-tree admits a planar straight-line drawing such that the local edge-length ratio is at most $4 + \varepsilon$ for any arbitrarily small positive $\varepsilon$. Several questions are naturally related with our results. We conclude the paper by listing some of those that, in our opinion, are among the most interesting ones.

• 1. Corollary 3 of this paper gives a logarithmic lower bound while Corollary 1 of [3] gives a sub-linear upper bound on the edge-length ratio of planar straight-line drawings of partial 2-trees. We find it interesting to close the gap between the upper and lower bound.

• 2. Theorem 2 gives an upper bound of 4 on the local edge-length ratio of partial 2-trees. It would be interesting to establish whether such an upper bound is tight. Also, studying the local edge-length ratio of other families of planar graphs is an interesting topic.

• 3. The construction in Theorem 2 creates drawings where the majority of angles are very close to 0 or $\pi$ radians. Hence, it would make sense to study the interplay between (local or global) edge-length ratio and angular resolution in planar straight-line drawings.