Discrete Comput Geom https://doi.org/10.1007/s00454-018-0001-5

On Planar Greedy Drawings of 3-Connected Planar Graphs Giordano Da Lozzo1 · Anthony D’Angelo2 · Fabrizio Frati1

Received: 11 November 2017 / Revised: 28 March 2018 / Accepted: 18 April 2018 © Springer Science+Business Media, LLC, part of Springer Nature 2018

Abstract A graph drawing is greedy if, for every ordered pair of vertices (x, y), there is a path from x to y such that the Euclidean distance to y decreases monotonically at every vertex of the path. Greedy drawings support a simple geometric routing scheme, in which any node that has to send a packet to a destination “greedily” forwards the packet to any neighbor that is closer to the destination than itself, according to the Euclidean distance in the drawing. In a greedy drawing such a neighbor always exists and hence this routing scheme is guaranteed to succeed. In 2004 Papadimitriou and Ratajczak stated two conjectures related to greedy drawings. The greedy embedding conjecture states that every 3-connected planar graph admits a greedy drawing. The convex greedy embedding conjecture asserts that every 3-connected planar graph admits a planar greedy drawing in which the faces are delimited by convex polygons. In 2008 the greedy embedding conjecture was settled in the positive by Leighton and

Editor in Charge: Kenneth Clarkson This research was partially supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), by MIUR Project “MODE” under PRIN 20157EFM5C, and by H2020-MSCA-RISE project 734922 – “CONNECT”. A preliminary version of this paper appeared at the 33rd International Symposium on Computational Geometry (SoCG 2017). Giordano Da Lozzo [email protected] Anthony D’Angelo [email protected] Fabrizio Frati [email protected] 1

Dipartimento di Ingegneria, Roma Tre University, 00146 Rome, Italy

2

School of Computer Science, Carleton University, Ottawa, ON K1S 5B6, Canada

123

Discrete Comput Geom

Moitra. In this paper we prove that every 3-connected planar graph admits a planar greedy drawing. Apart from being a strengthening of Leighton and Moitra’s result, this theorem constitutes a natural intermediate step towards a proof of the convex greedy embedding conjecture. Keywords Planar drawing · Greedy drawing · 3-Connected graph · Strong circuit graph Mathematics Subject Classification Primary 68R10 · Secondary 05C10

1 Introduction Geographic routing is a family of routing protocols for ad hoc networks, which are networks with no fixed infrastructure—such as routers or access points—and with dynamic topology [16,30,31]. In a geographic routing scheme each node of the network actively sends, forwards, and receives packets; further, it does so by only relying on the knowledge of its own geographic coordinates, of those of its neighbors, and of those of the packet destination. Greedy routing—originally called Cartesian routing [15]—is the simplest and most renowned geographic routing scheme. In this protocol, a node that has to send a packet simply forwards it to any neighbor that is closer—according to the Euclidean distance—to the destination than itself. The greedy routing scheme might fail to deliver packets because of the presence of a void in the network; this is a node with no neighbor closer to the destination than itself. For this reason, several variations of the greedy routing scheme have been proposed; see, e.g. [8,21,22]. Apart from its failure in the presence of voids, the greedy routing protocol has two disadvantages which limit its applicability. First, in order for the protocol to work, each node of the network has to be equipped with a GPS, which might be expensive and might consume excessive energy. Second, two nodes that are close geographically might be unable to communicate with each other because of the presence of topological obstructions. Rao et al. [29] introduced the following brilliant idea for extending the applicability of geographic routing in order to overcome the above issues. Suppose that a network topology is known; then one can assign virtual coordinates to the nodes and use these coordinates instead of the geographic locations of the nodes in the greedy routing protocol. The virtual coordinates can then be chosen so that the greedy routing protocol is guaranteed to succeed. Computing the virtual coordinate assignment for the nodes of a network corresponds to the following graph drawing problem: Given a graph G, construct a greedy drawing of G, that is a drawing in the plane such that, for any ordered pair of vertices (x, y), there exists a neighbor of x in G that is closer—in terms of Euclidean distance—to y than x. Equivalently, a greedy drawing of G is such that, for any ordered pair of vertices (x, y), there exists a distance-decreasing path from x to y, that is, a path (u 1 , u 2 , . . . , u m ) in G such that x = u 1 , y = u m , and the Euclidean distance between u i+1 and u m is smaller than the one between u i and u m , for any i = 1, 2, . . . , m − 2.

123

Discrete Comput Geom

Greedy drawings experienced a dramatical surge of popularity in the theory community in 2004, when Papadimitriou and Ratajczak [27] proposed the following two conjectures about greedy drawings of 3-connected planar graphs.1 Conjecture 1.1 (Greedy embedding conjecture) Every 3-connected planar graph admits a greedy drawing. Conjecture 1.2 (Convex greedy embedding conjecture) Every 3-connected planar graph admits a convex greedy drawing. Papadimitriou and Ratajczak [27,28] provided several reasons why 3-connected planar graphs are central to the study of greedy drawings. First, there exist non-3connected planar graphs and 3-connected non-planar graphs that do not admit any greedy drawing. Thus, the 3-connected planar graphs form the largest class of graphs that might admit a greedy drawing, in a sense. Second, all the graphs with no K 3,3 minor admit 3-connected planar spanning graphs, hence they admit a greedy drawing, provided the truth of the greedy embedding conjecture. Third, the study conducted by Papadimitriou and Ratajczak [27,28] provided evidence for the mathematical depth of their conjectures. In 2008 Leighton and Moitra [23,24] settled the greedy embedding conjecture in the affirmative; the same result was established (independently and slightly later) by Angelini et al. [4,5]. In this paper we show the following result. Theorem 1.3 Every 3-connected planar graph admits a planar greedy drawing. Given a 3-connected planar graph G, both the algorithm by Leighton and Moitra [23, 24] and the one by Angelini et al. [4,5] find a certain spanning subgraph S of G and construct a (planar) greedy drawing of S; then they embed the edges of G not in S as straight-line segments obtaining a, in general, non-planar greedy drawing of G. Thus, Theorem 1.3 strengthens Leighton and Moitra’s and Angelini et al.’s results. Furthermore, convex drawings, in which all faces are delimited by convex polygons, are planar, hence our theorem provides a natural step towards a proof of the convex greedy embedding conjecture. Our proof of Theorem 1.3 employs a structural decomposition for 3-connected planar graphs which finds its origins in a paper by Chen and Yu [9]. This decomposition actually works for a super-class of the 3-connected planar graphs known as strong circuit graphs. We construct a planar greedy drawing of a given strong circuit graph G recursively: We apply the structural decomposition to G in order to obtain some smaller strong circuit graphs, we recursively construct planar greedy drawings for them, and then we suitably arrange these drawings together to get a planar greedy drawing of G. For this arrangement to be feasible, we need to ensure that the drawings we construct satisfy some coercive geometric requirements; these are described in the main technical theorem of the paper—Theorem 3.4. Related results. Planar (and convex) greedy drawings always exist for maximal planar graphs [12]. Further, every planar graph G with a Hamiltonian path P = 1 The convex greedy embedding conjecture has not been stated in the journal paper by Papadimitriou and

Ratajczak [28]—it is only stated in the conference version of their paper [27].

123

Discrete Comput Geom

(u 1 , u 2 , . . . , u n ) has a planar (and convex) greedy drawing. Namely, construct a convex drawing  of G such that y(u 1 ) < y(u 2 ) < · · · < y(u n ); such a drawing always exists [19]. Scale  down horizontally, so that P is “almost vertical”. Then, for any 1 ≤ i < j ≤ n, the paths (u i , u i+1 , . . . , u j ) and (u j , u j−1 , . . . , u i ) are distance-decreasing. A characterization of the trees that admit a (planar) greedy drawing is known [25]; indeed, a greedy drawing of a tree is always planar [3]. Algorithms have been designed to construct succinct greedy drawings, in which the vertex coordinates are represented with a polylogarithmic number of bits [13,17, 18,32]; this has been achieved by allowing the embedding space to be different from the Euclidean plane or the metric to be different from the Euclidean distance. For example, Wang and He proved that every 3-connected planar graph admits a succinct convex drawing that is greedy with respect to a metric function based on parameters derived from Schnyder woods [32]. Planar graph drawings have been studied in which paths between pairs of vertices are required to exist satisfying properties different from being distance-decreasing. Consider a path P = (u 1 , u 2 , . . . , u m ) in a graph drawing. We say that P is selfapproaching [1,26] if, for any three points a, b, c in this order along P from u 1 to u m , the Euclidean distance between a and c is larger than the one between b and c—then a self-approaching path is also distance-decreasing. We say that P is increasingchord [1,11,26] if it is self-approaching in both directions—then an increasing-chord path is also self-approaching. Nöllenburg et al. [26] proved that every maximal planar graph admits a (possibly non-planar) drawing in which every pair of vertices is connected by an increasing-chord path and proved that every 3-connected planar graph admits a drawing in the hyperbolic plane in which every pair of vertices is connected by an increasing-chord path. We say that P is strongly monotone [2,14,20] if the orthogonal projections of the vertices of P on the line  through u 1 and u m appear in the order u 1 , u 2 , . . . , u m . Felsner et al. [14] proved that every 3-connected planar graph admits a planar drawing in which every pair of vertices is connected by a strongly monotone path.

2 Preliminaries In this section we introduce some preliminaries. For a graph G, we denote by V (G) and E(G) its vertex and edge sets, respectively. Subgraphs and connectivity. Let G be a graph and U ⊆ V (G); we denote by G − U the graph obtained from G by removing the vertices in U and their incident edges. Further, if e ∈ E(G), we denote by G − e the graph obtained from G by removing the edge e. Let H be a (not necessarily connected) subgraph of a graph G. An H -bridge B of G is either an edge of G not in H with both the end-vertices in H (then we say that B is a trivial H -bridge, see Fig. 1(a)), or a connected component of G − V (H ) together with the edges from that component to the vertices in V (H ) (then we say that B is a non-trivial H -bridge, see Fig. 1(b)); the vertices in V (H ) ∩ V (B) are the attachments

123

Discrete Comput Geom Fig. 1 (a) A trivial H -bridge and (b) a non-trivial H -bridge, enclosed in dotted curves. Empty disks represent attachments. In (b) H consists of three components, one of which is an isolated vertex

(a)

∈E (G)− E (H )

(b) ∈G− V (H ) H

H H

H

Fig. 2 The paths τuv (G) and βuv (G) in a 2-connected plane graph G

τ uv (G) u

v

G β uv (G)

of B in H . For a vertex v ∈ V (G) − V (H ), we denote by H ∪ {v} the subgraph of G composed of H and of the isolated vertex v. A vertex k-cut (in the following simply called k-cut) in a connected graph G is a set of k vertices whose removal disconnects G. For k ≥ 2, a connected graph is k-connected if it has no (k − 1)-cut. A k-connected component of a graph G is a maximal (with respect to both vertices and edges) k-connected subgraph of G. Given a 2-cut {a, b} in a 2-connected graph G, an {a, b}-component is either the edge ab (then we say that the {a, b}-component is trivial) or a subgraph of G induced by a, b, and the vertices of a connected component of G − {a, b} (then we say that the {a, b}-component is non-trivial). Plane graphs and embeddings. A drawing of a graph is planar if no two edges intersect except at common end-vertices. A plane graph is a planar graph together with a plane embedding; a plane embedding of a connected planar graph G is an equivalence class of planar drawings of G, where two drawings 1 and 2 are equivalent if: (i) for each v ∈ V (G), the clockwise order of the edges incident to v coincides in 1 and in 2 ; and (ii) the clockwise order of the edges composing the walks delimiting the outer faces of 1 and 2 is the same. When we talk about a planar drawing of a plane graph G, we always mean that it respects the plane embedding of G. We assume that any subgraph H of G is associated with the plane embedding obtained from the one of G by deleting vertices and edges not in H . In a plane graph G a vertex is external or internal depending on whether it is or it is not incident to the outer face of G, respectively. Refer to Fig. 2. For two external vertices u and v of a 2-connected plane graph G, let τuv (G) and βuv (G) be the paths composed of the vertices and edges encountered when walking along the boundary of the outer face of G in clockwise and counterclockwise direction from u to v, respectively. Note that τuv (G) and βvu (G) have the same vertices and edges, however in reverse linear orders. Geometry. In this paper every angle is measured in radians, even when not explicitly stated. The slope of a half-line  is defined as follows. Denote by p the starting point of  and let  be the vertical half-line starting at p and directed towards decreasing y-coordinates. Then the slope of  is the angle spanned by a counter-clockwise rotation

123

Discrete Comput Geom

around p bringing  to coincide with , minus π2 . Note that, because of this definition, the slope of any half-line is assumed to be between − π2 (included) and 3π 2 (excluded); in the following, there will be very few exceptions to this assumption, which will be however evident from the text. Every angle expressed as arctan(·) is assumed to be between − π2 and π2 . We define the slope of an edge uv in a graph drawing as the slope of the half-line from u through v. Note that the slope of an edge uv is equal to the slope of the edge vu plus or minus π . For a directed line , we let its slope be equal to the slope of any half-line starting at a point of  and directed as . We denote by pqr a triangle with vertices p, q, r , and we denote by  pqr the angle of pqr incident to q. Let  be a drawing of a graph G and let u, v ∈ V (G). We denote by d(, uv) the Euclidean distance between u and v in . We also denote by d H (, uv) the horizontal distance between u and v in , that is, the absolute value of the difference between the x-coordinates of u and v in ; analogously, dV (, uv) denotes the vertical distance between u and v in . With a slight abuse of notation, we will use d(, pq), d H (, pq), and dV (, pq) even if p and q are points in the plane (and not necessarily vertices of a graph). A drawing of a graph is a straight-line drawing if each edge is represented by a straight-line segment. The following lemma argues that the planarity and the greediness of a drawing are not lost as a consequence of any sufficiently small perturbation of the vertex positions. Lemma 2.1 Let  be a planar straight-line drawing of a graph G. There exists a value ε∗ > 0 such that the following holds true. Let   be any straight-line drawing of G in which, for every vertex z ∈ V (G), the Euclidean distance between the positions of z in  and   is at most ε∗ ; then   is planar and any path which is distance-decreasing in  is also distance-decreasing in   . Proof Let δ be the minimum Euclidean distance in  between any two vertices, or between any vertex and any non-incident edge, or between any two non-adjacent edges, where the Euclidean distance between a point p and a straight-line segment s is the minimum Euclidean distance between p and any point of s, and the Euclidean distance between two straight-line segments s1 and s2 is the minimum Euclidean distance between any point of s1 and any point of s2 . Note that δ > 0, since  is planar. Further, let γ = min {d(, uz) − d(, vz)}, where the minimum is taken over all the ordered triples (u, v, z) of  vertices of G such that d(, uz) > d(, vz).  distinct Note that γ > 0. Set ε∗ = min 3δ , γ5 . Note that ε∗ > 0. Consider any straight-line drawing   of G in which, for each vertex z ∈ V (G), the Euclidean distance between the positions of z in  and   is at most ε∗ . We prove that   is planar. In order to do that, we exploit the following observation. For any point p  that belongs to the straight-line segment s  representing an edge e in   , there exists a point p whose distance from p  is at most ε∗ and that belongs to the straight-line segment s representing e in . This is because s  is contained in the convex hull of the two disks with radius ε∗ centered at the end-points of s or, equivalently, in the region which is the Minkowski sum of s with a disk with radius ε∗ . Now suppose, for a contradiction, that in   two distinct vertices v1 and v2 coincide at a point p  , or an edge e overlaps a non-incident vertex v at a point p  , or two non-adjacent edges e1

123

Discrete Comput Geom Fig. 3 (a) Illustration for the statement of Lemma 2.2. (b) Illustration for the proof of Lemma 2.2

(a)

(b) 3

2

1

u2 u

u4

v 2 v 3 u 3= v 4

v

ui

slope s 1 W i W i+1 u i+1 u p slope s 3− π

and e2 cross at a point p  . Then there exist two points p1 and p2 in  that are at distance at most ε∗ from p  and hence at most 2ε∗ from each other and such that v1 and v2 are placed at p1 and p2 in , or such that v is placed at p1 and p2 belongs to the straightline segment representing e in , or such that p1 and p2 belong to the straight-line segments representing e1 and e2 in , respectively. However, 2ε∗ ≤ 2δ 3 < δ, which contradicts the definition of δ. We prove that any path P = (u 1 , u 2 , . . . , u m ) which is distance-decreasing in  is also distance-decreasing in   . Since P is distance-decreasing in , we have that d(, u i u m ) > d(, u i+1 u m ), for every i = 1, . . . , m − 2. Since the Euclidean distance between the positions of a vertex in  and   is at most ε∗ , for any i = 1, . . . , m −2 we have that d(  , u i u m ) ≥ d(, u i u m )−2ε∗ and that d(  , u i+1 u m ) ≤ d(, u i+1 u m ) + 2ε∗ . It follows that d(  , u i u m ) − d(  , u i+1 u m ) ≥ d(, u i u m ) − d(, u i+1 u m ) − 4ε∗ ≥ γ − 4ε∗ > 0. Hence, for i = 1, . . . , m − 2 we have that 

d(  , u i u m ) > d(  , u i+1 u m ). It follows that P is distance-decreasing in   . We conclude this section with a technical lemma we are going to exploit in the next section. Refer to Fig. 3(a). Lemma 2.2 Let G be a connected plane graph whose outer face consists of two simple paths (u = u 1 , u 2 , . . . , u p = v) and (u = v1 , v2 , . . . , vq = v), possibly sharing vertices with each other, and let  be a planar straight-line drawing of G. Let 1 , 2 , and 3 be three directed lines that pass through u and that have slopes s1 , s2 , and s3 , respectively, where 0 < s1 ≤ s2 ≤ s3 < π . Let sm (s M ) be the minimum (maximum, respectively) slope of an edge u i u i+1 or v j v j+1 . If s3 −π < sm ≤ s M < s1 (if s3 < sm ≤ s M < s1 + π ), then  lies entirely to the right (to the left, respectively) of 2 , except for the vertex u. Proof We only prove that, if s3 − π < sm ≤ s M < s1 , then  lies entirely to the right of 2 , except for the vertex u; the proof that, if s3 < sm ≤ s M < s1 + π , then  lies entirely to the left of 2 , except for the vertex u, is symmetric. Further, it suffices to prove that the paths (u = u 1 , u 2 , . . . , u p ) and (u = v1 , v2 , . . . , vq ) lie to the right of 2 , except for the vertex u; indeed, if that is the case, then the planarity of  implies that the entire drawing , except for the vertex u, lies to the right of 2 . We now prove that the path (u = u 1 , u 2 , . . . , u p ) lies to the right of 2 , except for the vertex u; the proof for the path (u = v1 , v2 , . . . , vq ) is analogous. For i = 1, . . . , p, let Wi be the open wedge delimited by the half-lines starting at u i with slopes s3 − π and s1 ; that is, Wi is the region of the plane that is spanned by a half-line starting at u i with slope s3 − π while rotating counter-clockwise around u i until it has slope s1 . We claim that Wi contains the path (u i , u i+1 , . . . , u p ) in its

123

Discrete Comput Geom Fig. 4 Structure of (G, u, v) in Case A

u1

u 0= u G1

u3

u2 G2

G3

u k− 1

uk = v Gk

interior, except for the vertex u i which is on the boundary of Wi . Observe that the claim, with i = 1, implies the lemma, since the interior of W1 lies to the right of 2 , given that s2 − π ≤ s3 − π and s1 ≤ s2 . We now prove the claim by reverse induction on i. The case i = p is trivial. Hence, assume that Wi+1 contains the path (u i+1 , u i+2 , . . . , u p ) in its interior, except for the vertex u i+1 which is on the boundary of Wi+1 . See Fig. 3(b). Since s3 − π < sm ≤ s M < s1 , the edge u i u i+1 lies in the interior of the wedge Wi , except for the vertex u i which is on the boundary of Wi . Further, since u i+1 lies in the interior of Wi , the entire wedge Wi+1 , and hence the path (u i+1 , u i+2 , . . . , u p ), lies in the interior of Wi . This completes the induction and the proof of the lemma. 

3 Proof of Theorem 1.3 In this section we prove Theorem 1.3. Throughout the section, we will work with plane graphs. Further, we will deal with a class of graphs that is wider than the one of 3-connected planar graphs. The graphs in this class have been introduced by Chen and Yu [9] with the name of strong circuit graphs, as they constitute a subclass of the well-known circuit graphs, whose definition is due to Barnette and dates back to 1966 [6]. Here we rephrase the definition of strong circuit graphs as follows. Definition 3.1 A strong circuit graph is a triple (G, u, v) such that either (i) G is an edge uv or (ii) |V (G)| ≥ 3 and the following properties are satisfied. (a) (b) (c) (d)

G is a 2-connected plane graph; u and v are two distinct external vertices of G; if the edge uv exists, then it coincides with the path τuv (G); and for every 2-cut {a, b} of G we have that a and b are external vertices of G and at least one of them is an internal vertex of the path βuv (G); further, every non-trivial {a, b}-component of G contains an external vertex of G different from a and b.

Several problems are more easily solved on (strong) circuit graphs than on 3connected planar graphs. This is because the (strong) circuit graphs can be easily decomposed into smaller (strong) circuit graphs, and hence are suitable for inductive proofs. We now present a structural decomposition for strong circuit graphs whose main ideas can be found in a paper by Chen and Yu [9] (see also a recent paper by Da Lozzo et al. [10] for an application of a specialized version of this decomposition to cubic strong circuit graphs). Consider a strong circuit graph (G, u, v) such that G is not a single edge uv. The decomposition distinguishes the case in which the path τuv (G) coincides with the edge uv (Case A) from the case in which it does not (Case B). Lemma 3.2 Suppose that we are in Case A (refer to Fig. 4). Then the graph G  = G − uv consists of a sequence of graphs G 1 , . . . , G k , with k ≥ 1, such that:

123

Discrete Comput Geom

(a)

(b)

u

v w

(c)

u w1

w2

v

B w3

u1 G1

u G2

u2

u4

u3 G3

G4

v G5

Fig. 5 (a) The BC-tree T  of G  contains a node with degree at least 3 corresponding to a 1-cut {w} of G  . (b) The BC-tree T  of G  contains a node with degree at least 3 corresponding to a 2-connected component B of G  . (c) The vertices u and v are not in G 1

– 3.2a: for i = 1, . . . , k − 1, the graphs G i and G i+1 share a single vertex u i ; further, G i is in the outer face of G i+1 and vice versa in the plane embedding of G; – 3.2b: for 1 ≤ i, j ≤ k with j ≥ i + 2, the graphs G i and G j do not share any vertex; and – 3.2c: for i = 1, . . . , k with u 0 = u and u k = v, (G i , u i−1 , u i ) is a strong circuit graph. Proof Consider the BC-tree T  of G  , which is the tree that is defined as follows. The tree T  contains a B-node for each 2-connected component of G  and a C-node for each 1-cut of G  ; further, T  contains an edge between a B-node b and a C-node c if the 1-cut corresponding to c is a vertex of the 2-connected component corresponding to b. First, we have that T  is a path. Namely suppose, for a contradiction, that T  has a node t with degree at least 3. If t corresponds to a 1-cut {w} of G  , as in Fig. 5(a), then w belongs to at least three 2-connected components of G  and the graph G  = G  − {w} consists of at least three connected components. Hence, the graph G  plus the edge uv is disconnected, which implies that {w} is a 1-cut of G; this contradicts property (a) of (G, u, v). Analogously, if t corresponds to a 2-connected component B of G  , as in Fig. 5(b), then B contains three distinct 1-cuts {w1 }, {w2 }, and {w3 } of G  ; for each i ∈ {1, 2, 3}, the removal of wi from G  disconnects G  into at least two connected components, at least one of which, denoted by G i , does not contain vertices of B. Since G 1 , G 2 , and G 3 share no vertex, the edge uv connects at most two components G i and G j with i, j ∈ {1, 2, 3}, which implies that {wh } is a 1-cut of G, where h = i, j and h ∈ {1, 2, 3}; this contradicts property (a) of (G, u, v). Hence T  is a path (b1 , c1 , b2 , c2 , . . . , bk−1 , ck−1 , bk ). Let G i be the 2-connected component of G  corresponding to the B-node bi and let {u i } be the 1-cut of G  corresponding to the C-node ci . Then, for i = 1, . . . , k − 1, the graphs G i and G i+1 share a single vertex u i , while for 1 ≤ i, j ≤ k with j ≥ i + 2 the graphs G i and G j do not share any vertex. The vertices u and v are one in G 1 and one in G k ; indeed, if say G 1 did not contain any of u and v, as in Fig. 5(c), then {u 1 } would be a 1-cut of G; this would contradict property (a) of (G, u, v). Assume, w.l.o.g. up to renaming, that u belongs to G 1 and v belongs to G k . We also have that u = u 1 , as if u = u 1 then {u 1 } would be a 1-cut of G, again contradicting property (a) of (G, u, v); analogously, v = u k−1 .

123

Discrete Comput Geom

We prove that G i+1 lies in the outer face of G i in the plane embedding of G, for every i = 1, . . . , k − 1. Suppose for a contradiction that, for some i ∈ {1, . . . , k − 1}, the graph G i+1 lies inside an internal face f of G i (except for the vertex u i , which is on the boundary of f ) in the plane embedding of G. Since the graphs G i+2 , . . . , G k do not share any vertex with G i , by planarity they all lie inside f . It follows that the vertex v lies inside f (note that v = u i even if k = i + 1, given that v = u k−1 ) and hence it is not incident to the outer face of G, which contradicts property (b) of (G, u, v). An analogous proof shows that G i lies in the outer face of G i+1 in the plane embedding of G, for every i = 1, . . . , k − 1. It remains to prove that, for every i = 1, . . . , k, the triple (G i , u i−1 , u i ) is a strong circuit graph, where u 0 = u and u k = v. We are going to use the fact that βuv (G) is composed of the paths βuu 1 (G 1 ), βu 1 u 2 (G 2 ), . . . , βu k−1 v (G k ). This is because uv coincides with τuv (G) by property (c) of (G, u, v) and because G i+1 lies in the outer face of G i and vice versa in the plane embedding of G. We now prove that (G i , u i−1 , u i ) satisfies properties (a)–(d) of a strong circuit graph. (a) Graph G i is 2-connected by assumption and it is associated with a plane embedding, given that it is a subgraph of the plane graph G. (b) For i = 1, . . . , k − 1, the vertex u i is external in the plane embedding of G i , since G i is in the outer face of G i+1 and vice versa; analogously, for i = 2, . . . , k, the vertex u i−1 is external in the plane embedding of G i . Further, u 0 = u and u k = v are external in the plane embeddings of G 1 and G k , respectively, since they are external in the plane embedding of G. Finally, for i = 1, . . . , k, the vertices u i−1 and u i are distinct, as otherwise {u i−1 = u i } would be a 1-cut of G, which would contradict property (a) of (G, u, v). (c) Suppose, for a contradiction, that the edge u i−1 u i exists and that it does not coincide with τu i−1 u i (G i ), for some i ∈ {1, . . . , k}, as in Fig. 6. This implies that G i contains vertices different from u i−1 and u i , and hence that {u i−1 , u i } is a 2-cut of G. The {u i−1 , u i }-component Hi of G that contains τu i−1 u i (G i ) is non-trivial, given that τu i−1 u i (G i ) does not coincide with the edge u i−1 u i . Further, no vertex of Hi other than u i−1 and u i is incident to the outer face of G, given that all the vertices of Hi other than u i−1 and u i lie inside the region delimited by the cycle βuu i−1 (G) ∪ u i−1 u i ∪ βu i v (G) ∪ vu. However, this contradicts property (d) of (G, u, v). (d) Consider any 2-cut {a, b} of G i ; then G i has at least two non-trivial {a, b}components. We prove that a and b are external vertices of G i . Suppose, for a contradiction, that a is an internal vertex of G i (the argument if b is an internal vertex of G i is analogous), as in Fig. 7(a). Then the cycle delimiting the outer face of G i belongs to a single {a, b}-component H of G i , and there is a non-trivial {a, b}-component H  = H of G i that does not contain any external vertices of G i other than b. Since all the edges in E(G) − E(G i ) lie in the outer face of G i in the plane embedding of G, it follows that {a, b} is a 2-cut of G, and that H  is a non-trivial {a, b}-component of G that does not contain any external vertices of G other than b. However, this contradicts property (d) of (G, u, v).

123

Discrete Comput Geom

u

Hi

u i− 1 β uu i− 1 (G)

ui

β u i v (G)

v

Fig. 6 Illustration for the proof that (G i , u i−1 , u i ) satisfies property (c) of a strong circuit graph: If the edge u i−1 u i exists and does not coincide with τu i−1 u i (G i ), then the {u i−1 , u i }-component Hi of G comprising τu i−1 u i (G i ) is non-trivial and contains no vertex incident to the outer face of G other than u i−1 and u i

(a)

b

(b)

(c) a

H

H a

u

u i− 1 β uu i− 1 (G)

H z also in H

b ui v β u i v (G)

b u

a= u i− 1 β uu i− 1 (G)

H

H ui

β u i v (G)

v

Fig. 7 Illustration for the proof that (G i , u i−1 , u i ) satisfies property (d) of a strong circuit graph. (a) A vertex a of a 2-cut {a, b} of G i is an internal vertex of G i . (b, c) The vertices a and b are both in τu i−1 u i (G i ). In (b) the {a, b}-component H of G i containing τab (G i ) contains an internal vertex z of βab (G i ), while in (c) H contains no internal vertex of βab (G i )

Next, we prove that at least one of a and b is an internal vertex of βu i−1 u i (G i ). Suppose, for a contradiction, that a and b are both in τu i−1 u i (G i ). Assume, w.l.o.g. up to renaming of a and b, that u i−1 , a, b, and u i appear in this order in τu i−1 u i (G i ), where possibly u i−1 = a and/or b = u i . Let H be the {a, b}-component of G i containing τab (G i ); let H  be any non-trivial {a, b}-component of G i different from H . – If H contains an internal vertex z of βab (G i ), as in Fig. 7(b), then it contains the paths βaz (G i ) and βzb (G i ), and hence it contains the entire cycle delimiting the outer face of G i . The planarity of G i implies that H  lies inside an internal face of H , except at the vertices a and b. This has two consequences. First, since all the edges in E(G) − E(G i ) lie in the outer face of G i (and of H ) in the plane embedding of G, the set {a, b} is a 2-cut of G and hence H  is a non-trivial {a, b}component of G. Second, no vertex of H  other than a and b is incident to the outer face of G i or to the outer face of G. These two statements contradict property (d) for (G, u, v). – If H contains no internal vertex of βab (G i ), as in Fig. 7(c), then it contains no vertex of βu i−1 u i (G i ) other than u i−1 and u i , given that βu i−1 u i (G i ) is a sub-path of βab (G i ); hence no edge in E(G) − E(G i ) is incident to a vertex of H different from a and b. Since the vertices of βu i−1 u i (G i ) are the only external vertices of G in V (G i ), it follows that H is a non-trivial {a, b}-component of G that contains no external vertex of G other than, possibly, a and b. This contradicts property (d) for (G, u, v). Finally, we prove that every non-trivial {a, b}-component H of G i contains an external vertex of G i different from a and b. Namely, if that is not the case for a non-trivial {a, b}-component H of G i , then no edge in E(G) − E(G i ) is incident to a vertex of H different from a and b. This implies that the set {a, b} is a 2-cut of G and H is a non-trivial {a, b}-component of G. However, no vertex of H other than,

123

Discrete Comput Geom Fig. 8 Structure of (G, u, v) in Case B

y1 y2

uk = v

H u 0= y

u

u1 u2 G1

(a)

u

(b)

H

yi

Bi

v

u

y1 H y

B1 B

Gk

G2

v

Fig. 9 (a) If there were exactly one H  -bridge Bi containing edges incident to the outer face of G, then yi would be a 1-cut of G. (b) The H  -bridges B1 and B of G

possibly, a and b is incident to the outer face of G. This contradicts property (d) for (G, u, v). 

Given a strong circuit graph (G, u, v) that is not a single edge, the vertex u belongs to one 2-connected component of the graph G −{v}. Indeed, if it belonged to more than one 2-connected component of G − {v}, then {u} would be a 1-cut of G − {v}, hence {u, v} would be a 2-cut of G, which would contradict property (d) for (G, u, v), given that neither u nor v is an internal vertex of βuv (G). We now present the following. Lemma 3.3 Suppose that we are in Case B (refer to Fig. 8). Let H be the 2-connected component of the graph G − {v} that contains u; then we have |V (H )| ≥ 3. Further, let H  denote the graph H ∪ {v}. Then G contains  distinct H  -bridges B1 , . . . , B , for some  ≥ 2, such that: – 3.3a: each H  -bridge Bi has two attachments, namely v and a vertex yi ∈ V (H ), where yi = u; – 3.3b: the H  -bridges B1 , . . . , B−1 are trivial, while B might be trivial or not; – 3.3c: any two among y1 , . . . , y are distinct except, possibly, for y−1 and y ; also if  = 2, then y1 and y2 are distinct; – 3.3d: y1 is an internal vertex of τuv (G); further, B1 is an edge that coincides with τ y1 v (G); – 3.3e: y is an internal vertex of βuv (G) and βuy1 (H ); further, B contains the path β y v (G); – 3.3f: B1 , . . . , B−1 appear in this counter-clockwise order around v and lie in the outer face of B in the plane embedding of G; – 3.3g: the triple (H, u, y1 ) is a strong circuit graph; and – 3.3h: B consists of a sequence of graphs G 1 , . . . , G k , with k ≥ 1, such that: • for i = 1, . . . , k − 1, the graphs G i and G i+1 share a single vertex u i ; further, G i is in the outer face of G i+1 and vice versa in the plane embedding of G; • for 1 ≤ i, j ≤ k with j ≥ i + 2, the graphs G i and G j do not share any vertex; and • for i = 1, . . . , k with u 0 = y and u k = v, the triple (G i , u i−1 , u i ) is a strong circuit graph.

123

Discrete Comput Geom

Proof We first prove that |V (H )| ≥ 3. Suppose, for a contradiction, that H is a single edge uy1 . If the degree of u in G is one, then {y1 } is a 1-cut of G; this contradicts property (a) for (G, u, v). Otherwise, u has a neighbor in V (G) − {u, v, y1 } (recall that the edge uv is not in G, since we are in Case B). Hence, there is a H  -bridge B of G that has u as an attachment. If B is trivial, then it coincides with the edge uv; however, this contradicts the hypothesis of Case B. Otherwise, B is non-trivial. Note that B does not contain y1 , as otherwise B would contain a path (not passing through v) between u and y1 , given that B is connected. However, this path would belong to H and not to B, given that H is a maximal 2-connected subgraph of G − {v}. It follows that {u, v} is a 2-cut of G, as the removal of u and v from G disconnects y1 from the vertices in V (B) − {u, v}; this contradicts property (d) for (G, u, v). We now prove the properties of the lemma, starting from 3.3a. First, if G had no H  -bridge, then it would not be connected, while it is 2-connected. Hence, G contains  distinct H  -bridges B1 , . . . , B with  ≥ 1. Each H  -bridge Bi has at most one attachment yi ∈ V (H ), as if Bi had at least two attachments in V (H ) then it would contain a path (not passing through v) between two vertices of H ; however, such a path would belong to H and not to Bi , given that H is a maximal 2-connected subgraph of G − {v}. Further, each H  -bridge Bi has at least one attachment yi ∈ V (H ), as otherwise v would be a 1-cut of G, whereas G is 2-connected. Hence, each H  -bridge Bi has one attachment yi ∈ V (H ). It follows that  ≥ 2, as if  = 1 then y1 would be a 1-cut of G, whereas G is 2-connected. Further, for i = 1, 2, . . . , , the vertex v is an attachment of Bi , as otherwise yi would be a 1-cut of G, whereas G is 2-connected. Suppose, for a contradiction, that yi = u, for some i ∈ {1, 2, . . . , }. If Bi is a trivial H  -bridge, then it coincides with the edge uv; however, this contradicts the fact that we are in Case B. If Bi is a non-trivial H  -bridge, then {u, v} is a 2-cut of G; namely, the removal of u and v from G disconnects the vertices in V (H ) − {u} from the vertices in V (Bi ) − {u, v}—the latter set is non-empty given that Bi is non-trivial. However, this contradicts property (d) for (G, u, v). It follows that yi = u, for i = 1, 2, . . . , . This proves 3.3a. We now prove properties 3.3b–3.3f. Since v is incident to the outer face of G, it lies in the outer face of H . It follows that all the H  -bridges B1 , . . . , B lie in the outer face of H , except at the vertices y1 , . . . , y , respectively. By the planarity of G, there are at most two H  -bridges among B1 , . . . , B that contain edges incident to the outer face of G. If there were only one H  -bridge Bi containing edges incident to the outer face of G, as in Fig. 9(a), then {yi } would be a 1-cut of G, whereas G is 2-connected. Hence, there are exactly two H  -bridges among B1 , . . . , B containing edges incident to the outer face of G. Denote them by B1 and B , as in Fig. 9(b), so that u, y1 , and y appear in this clockwise order along the outer face of H . Then y1 = y , as otherwise {y1 } would be a 1-cut of G, whereas G is 2-connected; in particular, y1 = y2 if  = 2. It also follows that y1 is an internal vertex of τuv (G), that y is an internal vertex of βuv (G) and βuy1 (H ), that B1 contains τ y1 v (G), that B contains β y v (G), and that no vertex yi = y1 , y is incident to the outer face of G. Now consider any H  -bridge Bi of G with yi = y . The graph Bi is a {yi , v}-component of G, however {yi , v} is a pair of vertices none of which is internal to βuv (G), hence if Bi were non-trivial, then property (d) of (G, u, v) would be violated. It follows that the only H  -bridges which might be non-trivial are those whose attachment in H is y ; in particular, since

123

Discrete Comput Geom

y1 = y , we have that B1 is trivial and coincides with the edge y1 v = τ y1 v (G). If there were at least two non-trivial H  -bridges whose attachment in H is y , then at least one of them (in fact all the ones different from B ) would be a {y , v}-component of G not containing any vertex incident to the outer face of G other than y and v; however, this would violate property (d) of (G, u, v). It follows that B is the only H  -bridge of G that is possibly non-trivial. By the planarity of G and the connectivity of B − {y , v}, all the trivial H  -bridges of G lie in the outer face of B ; denote them by B1 , . . . , B−1 in their counter-clockwise order around v. Since B1 , . . . , B−1 are trivial and incident to v, then y1 , . . . , y−1 are all distinct. By planarity and since y1 = y , it follows that B−1 and B are the only H  -bridges which might share their attachment in H . This concludes the proof of properties 3.3b–3.3f. We now prove 3.3g, that is, that the triple (H, u, y1 ) is a strong circuit graph. (a) Graph H is 2-connected by assumption and it is associated with a plane embedding, given that it is a subgraph of the plane graph G. (b) The vertex u is incident to the outer face of H since (G, u, v) satisfies (b). The vertex y1 is a vertex of τuv (G), as argued above, and hence it is incident to the outer face of G and to the one of H . Finally, u and y1 are distinct, as otherwise τuv (G) would coincide with the edge uv, contradicting the fact that we are in Case B. (c) Suppose, for a contradiction, that the edge uy1 exists and does not coincide with τuy1 (H ). Then {u, y1 } is a 2-cut of G, since the removal of u and y1 disconnects the internal vertices of τuy1 (H ) (which exist since τuy1 (H ) is not the edge uy1 ) from v. However, none of u and y1 is an internal vertex of βuv (G); this contradicts property (d) for (G, u, v). (d) The proof that (H, u, y1 ) satisfies (d) is very similar to the proof that (G i , u i−1 , u i ) satisfies (d) in Lemma 3.2. Consider any 2-cut {a, b} of H . If one of a and b is an internal vertex of H , then one non-trivial {a, b}-component L  of H lies inside an internal face of another non-trivial {a, b}-component L of H . This implies that {a, b} is a 2-cut of G and that L  is an {a, b}-component of G that does not contain any external vertices of G other than a or b; this contradicts property (d) for (G, u, v). It follows that a and b are external vertices of H . If a and b are both in τuy1 (H ), then assume that u, a, b, and y1 appear in this order in τuy1 (H ), where possibly u = a and/or b = y1 . Let L be the {a, b}-component of H containing τab (H ) and let L  be any non-trivial {a, b}-component of H different from L. If L contains an internal vertex of βab (H ), then it contains the entire cycle delimiting the outer face of H . It follows that L  lies inside an internal face of L, except at a and b, and hence that L  is an {a, b}-component of G that does not contain any external vertices of G other than a and b. This contradicts property (d) for (G, u, v). If L contains no internal vertex of βab (H ), then no edge in E(G) − E(H ) is incident to a vertex of L different from a and b. It follows that L is a non-trivial {a, b}component of G; further, neither a nor b is an internal vertex of βuv (G), given that V (τab (H )) ⊆ V (τuv (G)). This contradicts property (d) for (G, u, v). It follows that at least one of a and b is an internal vertex of βuy1 (H ).

123

Discrete Comput Geom Fig. 10 The graph B

uk = v y = u0

u1 u2 G1

Gk

G2

Finally, assume that a non-trivial {a, b}-component L of H contains no external vertex of H other than a and b. Then {a, b} is a 2-cut of G and L is a non-trivial {a, b}-component of G that contains no external vertex of G other than, possibly, a and b. This contradicts property (d) for (G, u, v). Hence, every non-trivial {a, b}component of H contains an external vertex of H other than a and b. This proves 3.3g for (H, u, y1 ). In order to prove 3.3h, assume that B is a non-trivial H  -bridge, i.e., it does not coincide with the edge y v, as otherwise there is nothing to prove. Let B be the plane graph obtained by adding the edge y v to B (note that the edge y v might or might not belong to G), so that y immediately precedes v in the clockwise order of the vertices along the outer face of B (both y and v are indeed incident to the outer face of B ); see Fig. 10. We prove that (B , y , v) is a strong circuit graph; then 3.3h follows by applying Lemma 3.2 to (B , y , v). (a) The graph B is associated with a plane embedding, given that it is a subgraph of the plane graph G. Further, y and v are both incident to the outer face of B , hence the plane graph B is well-defined. We prove that B is 2-connected. Since y and v are adjacent in B , they belong to the same 2-connected component of B . However, the only vertices of B that are incident to edges in E(G) − E(B ) are y and v. It follows that any 1-cut of B is also a 1-cut of G. Then B is 2-connected since G is. (b) The vertices y and v are distinct since the first one belongs to H , while the second one does not. Further, both y and v are incident to the outer face of B , as argued above, and hence are external vertices of B . (c) The edge y v exists and coincides with τ y v (B ), by construction. (d) Consider any 2-cut {a, b} of B (possibly {a, b} ∩ {y , v} = ∅). Since y v ∈ E(B ), we have that y and v are in the same {a, b}-component L of B . Since y and v are the only vertices of B incident to edges in E(G) − E(B ), it follows that {a, b} is also a 2-cut of G. Then a and b are external vertices of B since they are external vertices of G. Next suppose, for a contradiction, that neither a nor b is an internal vertex of β y v (B ). Since a and b are external vertices of B and since τ y v (B ) coincides with the edge y v, it follows that a = y and b = v (or vice versa). However, B is a {y , v}-component of G, hence the removal of y and v from B (or B ) does not disconnect B (or B ); this contradicts the assumption that {a, b} is a 2-cut of B , and implies that one of a and b is an internal vertex of β y v (B ). Finally, consider any non-trivial {a, b}-component L of B . As proven above, {a, b} is a 2-cut of G and at least one of a and b is not in {y , v}. If L contains the edge y v, then it contains an external vertex of B other than a and b, namely whichever vertex is in {y , v} − {a, b}. If L does not contain the edge y v, then L is also an

123

Discrete Comput Geom Fig. 11 Illustration for the statement of Theorem 3.4

bm = v

δ

u

Q x x Px α

u= b1 b2

bm− 1

b3

{a, b}-component of G and it contains an external vertex of B other than a and b since it contains an external vertex of G other than a and b. This concludes the proof that (B , y , v) is a strong circuit graph, hence it implies property 3.3h via Lemma 3.2. The lemma follows. 

We prove that any strong circuit graph (G, u, v) has a planar greedy drawing by exploiting Lemmas 3.2 and 3.3 in a natural way. Indeed, if we are in Case A (in Case B) then Lemma 3.2 (resp. Lemma 3.3) is applied in order to construct strong circuit graphs (G i , u i−1 , u i ) with i = 1, . . . , k (resp. strong circuit graphs (H, u, y1 ) and (G i , u i−1 , u i ) with i = 1, . . . , k) for which planar greedy drawings are inductively constructed and then combined together in order to get a planar greedy drawing of (G, u, v). The base case of the induction is the one in which G consists of a single edge. Then a planar greedy drawing of G is directly constructed. In order to be able to combine planar greedy drawings for the strong circuit graphs (G i , u i−1 , u i ) (and (H, u, y1 ) if we are in Case B) to construct a planar greedy drawing of (G, u, v), we need the inductively constructed drawings to satisfy some restrictive geometric requirements, which are expressed in the following theorem, which is the core of the proof of Theorem 1.3. Theorem 3.4 Let (G, u, v) be a strong circuit graph with at least three vertices and let 0 < α < π4 be an arbitrary parameter. Let βuv (G) = (u = b1 , b2 , . . . , bm = v). There exists a straight-line drawing  of G in the Cartesian plane such that the following holds. For any value δ ≥ 0, denote by δ the straight-line drawing obtained from  by moving the position of the vertex u by δ units to the left. Then δ satisfies the following properties (refer to Fig. 11). 1. δ is planar; 2. τuv (G) lies entirely on a horizontal line u with u to the left of v; 3. the edge b1 b2 has slope in the interval (−α; 0) and the edge bi bi+1 has slope in the interval (0; α), for each i = 2, 3, . . . , m − 1; 4. for every vertex x ∈ V (G) there is a path Px = (x = v1 , v2 , . . . , v p = v) from x to v in G such that the edge vi vi+1 has slope in the interval (−α; α) in δ , for each i = 1, 2, . . . , p − 1; further, if x = u, then u ∈ / V (Px ); 5. for every vertex x ∈ V (G) there is a path Q x = (x = w1 , w2 , . . . , wq = u) from x to u in G such that the edge wi wi+1 has slope in the interval (π − α; π + α) in δ , for each i = 1, 2, . . . , q − 1; and 6. for every ordered pair of vertices (x, y) in V (G) there is a path Px y from x to y in G / V (Px y ). such that Px y is distance-decreasing in δ ; further, if x, y = u, then u ∈ Before proceeding with the proof of Theorem 3.4, we comment on its statement. First, let us set δ = 0 and argue about 0 = . Properties 1 and 6 are those that one would expect, as they state that  is planar and greedy, respectively. Properties 2

123

Discrete Comput Geom Fig. 12 The straight-line drawing  of G in Case A if k=1

u

δ

d(Γ , a 1a2)

d(Γ , a 2at )

ε

a3

a2 u = a1= b1

b2

at = bm = v bm − 1

b3

and 3 state that all the edges incident to the outer face of  are “close” to horizontal; indeed, the edges of τuv (G) are horizontal, the edge b1 b2 has a slightly negative slope, and all the other edges of βuv (G) have slightly positive slopes. Since  is planar, this implies that  is contained in a wedge delimited by two half-lines with slopes 0 and −α starting at u. Properties 4 and 5 argue about the existence of certain paths from any vertex to u and v; these two vertices play an important role in the structural decomposition we employ, since distinct subgraphs are joined on those vertices, and the paths incident to them are inductively combined together in order to construct distance-decreasing paths. Finally, all these properties still hold true if u is moved by an arbitrary non-negative amount δ to the left. This is an important feature we exploit in one of our inductive cases. We now present an inductive proof of Theorem 3.4. In the Base Case the graph G is a single edge. Note that, although Theorem 3.4 assumes that the given graph has at least three vertices, for its proof we need to inductively draw certain subgraphs of it; these subgraphs might indeed be single edges. Whenever we need to draw a strong circuit graph (G, u, v) such that G is a single edge uv, we draw it as a horizontal straight-line segment with positive length, with u to the left of v. We remark that, since Theorem 3.4 assumes that |V (G)| ≥ 3, we do not need the constructed drawing to satisfy properties 1–6. We now discuss the inductive cases. Recall that in Case A the path τuv (G) coincides with the edge uv, while in Case B it does not. We discuss Case A first. Let G  = G −uv, where G  consists of a sequence of graphs G 1 , . . . , G k , with k ≥ 1, satisfying the properties described in Lemma 3.2. Our construction is different if k = 1 and k ≥ 2. Suppose first that k = 1; by Lemma 3.2 the triple (G  = G 1 , u, v) is a strong circuit graph (and G 1 is not a single edge, as otherwise G would have a double edge uv). Apply induction in order to construct a straight-line drawing   of G  with α2 as a parameter. Let τuv (G  ) = (u = a1 , a2 , . . . , at = v). By property 2 the path τuv (G  ) lies on a horizontal line u in   with u to the left of v. Let Y > 0 be the minimum distance in   of any vertex strictly below u from u . Let ε=

  1 min ε∗  , Y, tan(α) · d(  , a1 a2 ), tan(α) · d(  , a2 at ) , 2

where ε∗  > 0 is the value from Lemma 2.1. We construct a straight-line drawing  of G from   as follows; refer to Fig. 12. Decrease the y-coordinate of the vertex a2 by ε. Further, decrease the y-coordinate of the vertex ai , with i = 3, 4, . . . , t − 1, so that it ends up on the straight-line segment a2 at . Draw uv as a straight-line segment. This completes the construction of . Before proving that the drawing δ —for any δ ≥ 0—satisfies properties 1–6 of Theorem 3.4, we give a few comments on the construction.

123

Discrete Comput Geom

A useful observation is that the position of any vertex of G in  is “very close” to—in fact at most ε apart from—its position in   ; indeed, since ε < ε∗  , Lemma 2.1 implies properties 1 and 6 for . Property 3 is trivially verified by , given that βuv (G) = βuv (G  ) has the same representation in  and   . Property 2 is also easily shown to be satisfied by , since τuv (G) coincides with the edge uv. The paths Px and Q x in G satisfying properties 4 and 5 are respectively constructed from the paths Px and Q x in G  satisfying the same properties; however, Px and Q x might also contain sub-paths of τuv (G  ). Here we use ε < tan(α)·d(  , a1 a2 ) and ε < tan(α)·d(  , a2 at ) in order to prove that the edges of τuv (G  ) have slopes in (−α; α) when traversed from u to v and in (π − α; π + α) when traversed from v to u. The line of argument above is complicated by the fact that properties 1–6 of Theorem 3.4 have to be proven for δ , for any δ ≥ 0, and not only for 0 = . For example, while it is true that the position of any vertex of G in δ is at most ε apart from its position in δ , it is not guaranteed that ε < ε∗  , hence the planarity and the δ greediness of δ do not directly follow from Lemma 2.1. We now prove the following. Lemma 3.5 For any δ ≥ 0, the drawing δ constructed in Case A if k = 1 satisfies properties 1–6 of Theorem 3.4. Proof We prove that δ satisfies properties 1–6 of Theorem 3.4. Property 1. Note first that  = 0 is planar, given that ε < ε∗  . We prove that δ is planar, for any δ > 0. Since δ and  coincide, except for the position of the vertex u, we only need to prove that no edge incident to u crosses or overlaps any other edge in δ . Then consider any two edges uu  and ww  with u  , w, w  ∈ V (G) (possibly w = u or w = u  ) and suppose, for a contradiction, that they cross or overlap in δ . Case 1. If u  = v, then uu  and ww  do not cross or overlap in δ , given that no vertex other than u and v lies on or above u in δ . Case 2. If u  = v, then we have y(u  ) < y(u) in δ . By properties 1–3, we have that   lies in the closed wedge that is delimited by the half-lines starting at u with slopes 0 and − π4 . It follows that x(u) is smaller than the x-coordinate of every other vertex in   , , and δ (given that every vertex has the same x-coordinate in   , , and δ , except for u, whose x-coordinate might be smaller in δ than in   and ). Case 2.1. Suppose first that w = u. Then uu  and ww  do not cross in δ , for any δ > 0, as they share a vertex. Suppose, for a contradiction, that uu  and ww  overlap in δ , for some δ > 0. We have w  = v, by the same observation as in Case 1. We distinguish four cases. – Case 2.1.1. If u  , w  ∈ V (τuv (G  )), then by property 2 we have that the vertices u  and w  lie on u in   . However, since x(u) < x(u  ) and x(u) < x(w  ), it follows that the edges uu  and ww  overlap in   , a contradiction to property 1 of   . / V (τuv (G  )), then we further distinguish – Case 2.1.2. If u  ∈ V (τuv (G  )) and w  ∈ two cases. Note that when transforming   into , the y-coordinate of u  has been decreased by a value εu  . • Case 2.1.2.1. Suppose first that x(w  ) < x(u  ) in   , , and δ (see Fig. 13(a)). By construction we have εu  ≤ ε; further, by definition of ε we have ε < Y ; moreover, by definition of Y we have Y ≤ εw , where εw is the distance

123

Discrete Comput Geom

(a)

u= w u

δ

(b)

u= w εw w

εu u

pu

δ

qu

u

xu

qu εu εx pu

w

Fig. 13 Illustration for property 1 in Cases 2.1.2.1 (a) and 2.1.2.2 (b)

between w  and u in   (and in δ ). It follows that y(w  ) < y(u  ) in δ . The inequalities x(u) = x(w) < x(w  ) < x(u  ) and y(w  ) < y(u  ) < y(u) = y(w) imply that the edges uu  and ww  do not overlap in δ . • Case 2.1.2.2. Suppose next that x(u  ) ≤ x(w  ) in   , , and δ (see Fig. 13(b)). Let pu (qu ) be the point where u lies in δ (resp. in   ). Analogously, let pu  (qu  ) be the point where u  lies in δ (resp. in   ). Since x(u) = x(w) < x(u  ) ≤ x(w  ), we have that uu  and ww  overlap in δ if and only if pu  is a point of the straight-line segment pu w  . Since x( pu ) < x(qu ) < x(qu  ), it follows that the straight-line segment qu w  intersects the vertical straightline segment pu  qu  in a point xu . Let εx be the distance between xu and u . Since xu is a point of pu  qu  , we have εx ≤ εu  . By construction, we have εu  ≤ ε; further, by definition of ε, we have ε < ε∗  . This is a contradiction to the definition of ε∗  , since the drawing obtained from   by decreasing the y-coordinate of u  by εx < ε∗  is not planar, as the edges uu  and ww  overlap. / V (τuv (G  )) and w  ∈ V (τuv (G  )) can be – Case 2.1.3. The case in which u  ∈ discussed as Case 2.1.2, with inverted roles for u  and w  . / V (τuv (G  )), then u = w, u  , and w  have the – Case 2.1.4. Finally, if u  , w  ∈  same positions in δ and δ . Then uu  and ww  overlap in δ . This contradicts property 1 of   . Case 2.2. Suppose next that w = u  . Then uu  and ww  do not cross in δ , for any δ > 0, as they share a vertex. Suppose, for a contradiction, that uu  and ww  overlap in δ , for some δ > 0. Case 2.2.1. If w  = v, then uu  and ww  do not actually overlap in δ , given that u and w  both lie on u , while w = u  lies below u . Case 2.2.2. If w  = v, then we further distinguish four cases. – Case 2.2.2.1. If u  , w  ∈ V (τuv (G  )), then by property 2 we have that the vertices u  = w and w  lie on u in   . Since   is planar, we have x(u) < x(u  ) = x(w) < x(w  ). Since the x-coordinates of u  = w and w  do not change when transforming   into δ , and since the x-coordinate of u in δ is smaller than in   , it follows that the edges uu  and ww  lie to the left and to the right of the vertical line through u  = w, respectively, hence they do not overlap in δ , a contradiction. / V (τuv (G  )), then note that when – Case 2.2.2.2. If u  ∈ V (τuv (G  )) and w  ∈  transforming  into , the y-coordinate of u  has been decreased by a value εu  . By construction we have εu  ≤ ε; further, by definition of ε we have ε < Y ; moreover, by definition of Y we have Y ≤ εw , where εw is the distance between w  and u in   (and in δ ). It follows that y(w  ) < y(w) = y(u  ) < y(u) in

123

Discrete Comput Geom Fig. 14 Illustration for property 1 in Case 2.3

u u

u

δ

u

εw w

εu u

δ . Hence, the edges uu  and ww  lie above and below the horizontal line through u  = w, respectively, thus they do not overlap in δ , a contradiction. – Case 2.2.2.3. If u  ∈ / V (τuv (G  )) and w  ∈ V (τuv (G  )), then we further distinguish two cases. • Case 2.2.2.3.1. Suppose that x(u  ) = x(w) < x(w  ) in   , , and δ . Since x(u) < x(u  ), it follows that the edges uu  and ww  lie on opposite sides of the vertical line through u  = w, thus they do not overlap in δ , a contradiction. • Case 2.2.2.3.2. Suppose next that x(w ) ≤ x(u  ) = x(w) in   , , and δ . Then a contradiction can be derived similarly to Case 2.1.2.2. Indeed, if uu  and ww  overlap in δ , then w  lies on the straight-line segment uu  . However, this implies that by decreasing the y-coordinate of w in   by a suitable amount smaller than ε, the edges uu  and ww  overlap, which is a contradiction to the fact that ε < ε∗  . – Case 2.2.2.4. Finally, if u  , w  ∈ / V (τuv (G  )), then u, w = u  , and w  have the  same positions in δ and δ . Then uu  and ww  overlap in δ . This contradicts property 1 of   . Case 2.3. Suppose finally that w, w = u, u  . Refer to Fig. 14. Consider the unbounded region R of the plane that is delimited by u from above, by the horizontal line u  through u  from below, and by the representation of the edge uu  in  from the right. For any δ > 0, we have that uu  lies in the interior of R (except at points u and u  ) in δ , hence if uu  and ww  cross in δ then at least one end-vertex of ww  , say w, lies in the interior of R, given that y(w), y(w ) ≤ y(u) and that ww  does not cross uu  in . This implies that x(u) < x(w) < x(u  ) in   , , and δ . We now distinguish four cases. – Case 2.3.1. If u  , w ∈ V (τuv (G  )), then by property 2 we have that u  and w lie on u in   . However, since x(u) < x(w) < x(u  ), it follows that the edge uu  overlaps the vertex w in   , a contradiction to property 1 of   . / V (τuv (G  )), then when transforming   – Case 2.3.2. If u  ∈ V (τuv (G  )) and w ∈  into  the y-coordinate of u has been decreased by a value εu  ≤ ε which is larger than the distance εw ≥ Y between w and u . This contradicts ε ≤ Y2 < Y . / V (τuv (G  )) and w ∈ V (τuv (G  )), then when transforming   – Case 2.3.3. If u  ∈ into  the y-coordinate of w has been decreased by a value εw ≤ ε. The point p on the edge uu  with x-coordinate equal to x(w) has y-coordinate larger than y(w), hence the distance from p to u is a value ε p < εw . This implies that the drawing obtained from   by decreasing the y-coordinate of w by ε p , while every other vertex stays put, is not planar, given that the edge uu  overlaps the vertex w. However, since ε p < εw , this contradicts εw ≤ ε < ε∗  . / V (τuv (G  )), then u, u  and w have the same positions – Case 2.3.4. Finally, if u  , w ∈   in δ and δ . Then uu and ww  cross or overlap in δ . This contradicts property 1 of   .

123

Discrete Comput Geom

Property 2. Note that u and v lie on the same horizontal line u (with u to the left of v) in  since they do in   and since they have not been moved when transforming   into . Since τuv (G) coincides with the edge uv, it follows that δ satisfies property 2. Property 3. This property is satisfied by δ since it is satisfied by δ and since no vertex of βuv (G  ) = βuv (G) moves when transforming   into  (indeed, τuv (G  ) and βuv (G  ) do not share any vertex other than u and v, given that G  is 2-connected). Property 4. Let x ∈ V (G). If x = u, let Px = (u, v); then the only edge of Px has slope 0 ∈ (−α; α). If x = u, then let Px = (x = v1 , v2 , . . . ,v p = v) be a path in G  such that the slope of vi vi+1 in   is in the interval − α2 ; α2 , for i = 1, . . . , p − 1, and such that u ∈ / V (Px ). This path exists since   satisfies property 4, by induction. We distinguish two cases. – If no vertex of Px − {v} belongs to τuv (G  ), then Px = Px satisfies the required properties. Indeed, no vertex other than those internal to τuv (G  ) moves when transforming   into  and no vertex other than u moves when transforming  into δ ; thus, Px has the same representation (and in particular each edge of Px has the same slope) in   and δ . – Otherwise, a vertex of Px − {v} belongs to τuv (G  ); let h be the smallest index such that vh = a j , for some a j ∈ V (τuv (G  )) − {v}, and define Px = (x = / V (Px ), v1 , v2 , . . . , vh = a j , a j+1 , . . . , at = v). Refer to Fig. 15. Note that u ∈ given that u ∈ / V (Px ). Hence, it suffices to argue about the slopes of the edges of Px in  (rather than in δ ). • First, for i = 1, . . . ,h − 2, the slope of the edge vi vi+1 is in (−α; α) in  since it is in − α2 ; α2 ⊂ (−α; α) in   and since neither vi nor vi+1 moves when transforming   into . • Second,  forε i = j, . . . , t − 1, the slope of the edge ai ai+1 in  is , which is in the interval (0; α) ⊂ (−α; α), given that arctan d(  ,a 2 at )  ε, d( , a2 at ) > 0 and that ε < tan(α) · d(  , a2 at ).  , respectively. • Third, let s  and s be the slopes of theedge vh−1  vh in  and α α   Since vh−1 vh ∈ E(Px ), we have s ∈ − 2 ; 2 ; since α ≤ π4 , this implies that x(vh−1 ) < x(vh ) in   and  (note that the x-coordinates of the vertices do not change when transforming   into ). Further, by properties 1–3 of   , we have that vh−1 lies below u , which contains vh ; hence, y(vh−1 ) < y(vh ) in   . Since the vertex vh moves down, while vh−1 stays put, when transforming   into , we have that s < s  . Further, since ε ≤ Y2 < dV (  , vh−1 vh ), we  have  α that y(vh−1 ) < y(vh ) in . It follows that s > 0; hence s ∈ (0; s ) ∈ 0; 2 ⊂ (−α; α). Property 5. Let x ∈ V (G) and let Q x = (x = w1, w2 , . . . , wq = u) be a path in δ such that the slope of wi wi+1 is in π − α2 ; π + α2 , for i = 1, 2, . . . , q − 1. This path exists since δ satisfies property 5, by induction. Similarly to the proof that δ satisfies property 4, we distinguish two cases. If no vertex of Q x − {u} belongs to τuv (G  ), then let Q x = Q x and observe that Q x satisfies the required properties in δ since Q x does in δ . Otherwise, let h be the smallest index such that wh = a j , for some a j ∈

123

Discrete Comput Geom d(Γ , a 2at )

Fig. 15 Illustration for the proof that the slope in δ of every edge in the path Px = (x = v1 , v2 , . . . , vh = a j , a j+1 , . . . , at = v) is in (−α; α). The path Px is thick

x = v1

ε a2

vh− 1

v h = aj

at = v

u

V (τuv (G  )) − {u}, and define Q x = (x = w1 , w2 , . . . , wh = a j , a j−1 , . . . , a1 = u). Refer to Fig. 16. – First, for i = 1, . . . , h − 2, the slope of the edge wi wi+1 is in (π − α; π + α) in δ since it is in π − α2 ; π + α2 ⊂ (π − α; π + α) in δ . – Second, we argue about the slope s of the edge wh−1 wh in δ . By definition of the index h, the vertices wh−1 and wh are both different from u, hence s coincides with the slope of the edge wh−1 wh in . Let s  be  the slope of the  edge wh−1 wh in   . Since wh−1 wh ∈ Q x , we have that s  ∈ π − α2 ; π + α2 ; since α ≤ π4 , this implies that x(wh−1 ) > x(wh ) in   and  (note that the x-coordinates of the vertices do not change when transforming   into ). Further, by properties 1–3 of   , we have that wh−1 lies below u , which contains wh ; hence, y(wh−1 ) < y(wh ) in   . Since the vertex wh moves down, while wh−1 stays put, when transforming   into , we have that s > s  . Further, since ε ≤ Y2 < dV (  , wh−1 wh ), we  have that y(w  h−1 ) < y(wh ) in . It follows that s < π ; hence s ∈ (s ; π ) ∈  α π − 2 ; π ⊂ (π − α; π + α).   ε , – Third, for i = j, j − 1 . . . , 3, the edge ai ai−1 has slope π + arctan d(  ,a 2 at ) which is larger than π , given that ε, d(  , a2 at ) > 0, and smaller than π + α, given that ε < tan(α) · d(  , a2 at ).   – Fourth, the edge a2 a1 has slope π − arctan δ+d(ε ,a1 a2 ) , which is smaller than π , given that ε, d(  , a1 a2 ) > 0 and δ ≥ 0, and larger than π − α, given that ε ε  δ+d(  ,a1 a2 ) ≤ d(  ,a1 a2 ) and that ε < tan(α) · d( , a1 a2 ). Property 6. Consider any two vertices x, y ∈ V (G). – First, assume that x, y = u. By induction, there exists a path Px y from x to y in G  that is distance-decreasing in   with u ∈ / V (Px y ). By Lemma 2.1 and since, for every vertex z ∈ V (G), the Euclidean distance between the positions of z in   and  is at most ε < ε∗  , we have that Px y is also distance-decreasing in . Further, since all the vertices other than u have the same position in  and δ , it follows that Px y is a distance-decreasing path from x to y not passing through u in δ . – Second, suppose that y = u. Consider the path Q x in G from property 5, which connects x with y = u and whose every edge has slope in (π − α; π + α) in δ . u

δ

d(Γ , a 1a2)

d(Γ , a 2at ) ε

u= a1

a2

w h = aj w h− 1

x = w1

Fig. 16 Illustration for the proof that the slope in δ of every edge in the path Q x = (x = w1 , w2 , . . . , wh = a j , a j−1 , . . . , a1 = u) is in (π − α; π + α). The path Q x is thick

123

Discrete Comput Geom

u

δ

d(Γ1, u 0u 1) ε

u= u 0= b1

Γ1

u1

Γ2

u2

Γ3

u3

Γ4

h pv = v= u 4= bm

b2

Fig. 17 The straight-line drawing  of G in Case A if k ≥ 2. In this example k = 4. The gray angle in the drawing is α2

Since α ≤ π4 , it follows that Q x is a π -path (according to the definition in [11]) or is π -monotone (according to the definition in [7]), where for some angle β a path or equivalently is β-monotone if every edge qi qi+1 has (q1 , q2 , . . . , qr ) is a β-path   slope in the interval β − π4 ; β + π4 . In [11, Lemma 3] it is proven that a β-path is distance-decreasing in both directions (in fact, it satisfies a stronger property, namely it is increasing-chord); hence, Q x is distance-decreasing in δ . – Finally, suppose that x = u. Consider the path Q y in G from property 5, which connects y with x = u and whose every edge has slope in (π − α; π + α) in δ . As discussed in the case above for Q x , we have that Q y is a π -path, hence it is distance-decreasing in both directions. Hence, Q y is distance-decreasing in δ when traversed from x = u to y. This concludes the proof of the lemma.



We now discuss the case in which k ≥ 2. Refer to Fig. 17. By Lemma 3.2, for i = 1, . . . , k, the triple (G i , u i−1 , u i ) is a strong circuit graph, where u 0 = u, u k = v, and u i is the only vertex shared by G i and G i+1 , for i = 1, . . . , k − 1. If G 1 is a single edge, then apply induction in order to construct a straight-line drawing 1 of G 1 and define ε = 21 min {ε∗ 1 , tan(α) · d(1 , u 0 u 1 )}. If G 1 is not a single edge, then apply induction in order to construct a straight-line drawing 1 of G 1 with α2 as a parameter. By property 2 of 1 , the path τu 0 u 1 (G 1 ) lies on a horizontal line u . Let Y > 0 be the minimum distance in 1 of any vertex strictly below u from u . Let ε = 21 min {ε∗ 1 , Y, tan(α) · d(1 , u 0 u 1 )}. In both cases, decrease the y-coordinate of u 1 by ε. Further, decrease the y-coordinate of every internal vertex of the path τu 0 u 1 (G 1 ), if any, so that it ends up on the straight-line segment u 0 u 1 . Now consider a half-line h with slope s = α2 starting at u 1 . Denote by pv the point at which h intersects the horizontal line u through u. For i = 2, . . . , k, apply induction in order to construct a straight-line drawing i of G i with α3 as a parameter (if G i is a single edge, then the parameter does not matter). Uniformly scale the drawings 2 , . . . , k so that the Euclidean distance between u i−1 and u i is equal 1 ,u 1 pv ) to d(k−1 . For i = 2, . . . , k, rotate the scaled drawing i around u i−1 counterclockwise by s radians. Translate the scaled and rotated drawings 2 , . . . , k so that the representations of u i in i and i+1 coincide, for i = 1, . . . , k − 1. Finally, draw the edge uv as a straight-line segment. This completes the construction of a drawing  of G. Before proving that the drawing δ —for any δ ≥ 0 – satisfies properties 1–6 of Theorem 3.4, we give a few comments on the construction. Property 1 of δ is guaranteed by two facts. First, the drawing of the graph G i , for each i = 1, . . . , k, is planar. This is trivial for the graphs G 2 , . . . , G k , whose representations in δ are inductively constructed (and then scaled, rotated, and translated); further, the arguments for proving that the drawing of G 1 in δ is planar are very similar to those used in the proof of Lemma 3.5. Second, the drawings of G 1 , . . . , G k in δ

123

Discrete Comput Geom

are “horizontally separated”, that is, the vertical line through the vertex u i keeps the drawings of G 1 , . . . , G i to its left and those of G i+1 , . . . , G k to its right; hence, no two distinct graphs among G 1 , . . . , G k cross each other. While property 2 is easily shown to be satisfied by δ , since τuv (G) coincides with the edge uv, the proof of property 3 needs some efforts. First, the fact that 2 , . . . , k are inductively constructed with parameter α3 ensures that, for any i = 2, . . . , k, every edge in βu i−1 u i (G i ) has slope in   the interval − α3 ; α3 in i ; the subsequent rotation of α2 brings that slope in the interval  α 5α  6 ; 6 , and hence in the desired interval (0; α). Second, the slope in δ of any edge of βu 0 u 1 (G 1 ) is in the desired interval, which is either (−α; 0) if the edge is incident to u 0 , or (0; α) otherwise. This statement easily comes from induction if the edge is not incident to u 1 ; otherwise, one has to exploit that ε < tan(α) · d(1 , u 0 u 1 )—if G 1 is a single edge—or that ε < Y —if G 1 is not a single edge. The paths Px , Q x , and Px y proving that properties 4–6 are satisfied by δ are obtained by suitably combining paths satisfying the drawings of G 1 , . . . , G k in δ , together k properties 4–6 in  k τul−1 ul (G l ) and l=1 βul ul−1 (G l ). For example, a path Px y with sub-paths of l=1 satisfying property 6 and connecting a vertex x of G i with a vertex y of G j , with 2 ≤ i < j ≤ k, is composed of a path from x to u i satisfying property 4 in i , plus  j−1 the path l=i+1 τul−1 ul (G l ) from u i to u j−1 , plus the reverse of a path from y to u j−1 satisfying property 5 in  j . All these paths are indeed “almost flat” in δ . We now prove the following. Lemma 3.6 For any δ ≥ 0, the drawing δ constructed in Case A if k ≥ 2 satisfies properties 1–6 of Theorem 3.4. Proof Throughout the proof, we denote by 1,δ the drawing obtained from 1 by moving the position of the vertex u 0 = u by δ units to the left (where 1 is understood as the drawing of G 1 in which the vertices of τu 0 u 1 (G 1 ) all lie on u ). Property 2. We start by proving that u and v lie on the same horizontal line. Because of the uniform scaling which has been applied to 2 , . . . , k , we have that d(, u i−1 u i ) = d(,u 1 pv ) for i = 2, . . . , k. Since the vertices u 1 , . . . , u k all lie on h, we have that k−1

1 pv ) for i = 2, . . . , k. Hence, the y-coordinate of v = u k is dV (, u i−1 u i ) = dV (,u k−1 equal to y(u 1 ) + dV (, u 1 pv ) = y(u), which implies that u and v lie on the horizontal line u in  and δ . Further, u is to the left of v in , given that 1 satisfies property 2 and that 0 < s < π2 . Since τuv (G) coincides with the edge uv, it follows that δ satisfies property 2.

Property 3. Note that βuv (G) = βu 0 u 1 (G 1 ) ∪ βu 1 u 2 (G 2 ) ∪ · · · ∪ βu k−1 u k (G k ). We first argue about the slope of the edge b1 b2 . – If G 1 is a single edge u 0 u 1 , then we  have u 0 =b1 and u 1 = b2 . Then the slope of the edge b1 b2 in δ is − arctan δ+d(ε1 ,u 0 u 1 ) , which is smaller than 0, given that ε, d(1 , u 0 u 1 ) > 0 and δ ≥ 0, and larger than −α, given that δ ≥ 0 and that ε < tan α · d(1 , u 0 u 1 ), hence it is in (−α; 0). – If G 1 has more than two vertices, then βu 0 u 1 (G 1 ) is not a single edge u 0 u 1 , by property (c) of (G 1 , u 0 , u 1 ); hence, u 0 = b1 and b2 = u 1 . Since 1,δ satisfies property 3 and since u 1 is the only vertex of βu 0 u 1 (G 1 ) whose positions in 1,δ

123

Discrete Comput Geom

and δ do not coincide, it follows  slope of b1 b2 in δ is in the interval  that the (−α; 0) since it is in the interval − α2 ; 0 ⊂ (−α; 0) in 1,δ . We now argue about the slope s j of the edge b j b j+1 in δ , for any j = 2, . . . , m −1. – If b j b j+1 coincides with a graph G i , for some i ∈ {2, . . . , k}, then s j = s = α 2 ∈ (0; α). Note that, because of the assumption j ≥ 2, the edge b j b j+1 cannot coincide with the graph G 1 . – If b j b j+1 belongs to a graph G i with |V (G i )| ≥ 3, with i ≥ 2, and with b j = u i−1 (the last condition implies that b j b j+1 is not the first edgeof βu i−1 u i (G i )), then s j is given by the slope b j b j+1 has in i , which is in 0; α3 by property 3 of i ,   plus s, which results from the rotation of i . Hence s j ∈ α2 ; 5α 6 ⊂ (0; α). – If b j b j+1 belongs to a graph G i with |V (G i )| ≥ 3, with i ≥ 2, and with b j = u i−1 (the last condition implies that b j b j+1 is the first  edge of βu i−1 u i (G i )), then s j is given by the slope b j b j+1 has in i , which is in − α3 ; 0 by property 3 of i , plus   s, which results from the rotation of i . Hence s j ∈ α6 ; α2 ⊂ (0; α). – If b j b j+1 belongs to G 1 , if |V (G 1 )| ≥ 3, and if b j+1 = u 1 (the last condition implies that b j b j+1 is not the last edge of βu 0 u 1 (G 1 )), then since 1,δ satisfies property 3 and since u 1 is the only vertex of βu 0 u 1 (G 1 ) whose positions in 1,δ and δ do not coincide, it follows that s j ∈ (0; α) since the slope of b j b j+1 in 1,δ is in 0; α2 ∈ (0; α). – Finally, assume that b j b j+1 belongs to G 1 , that |V (G 1 )| ≥ 3, and that b j+1 = u 1 (the last condition implies that b j b j+1 is the last edge of βu 0 u 1 (G 1 )). Note that b j = u, given that j ≥ 2, hence by property 3 of 1 we have that the slope of  the edge b j b j+1 in 1 is in 0; α2 , thus we have that x(b j ) < x(b j+1 ) and that y(b j ) < y(b j+1 ) in 1 . The positions of b j in 1 and δ coincide, given that / V (τu 0 u 1 (G 1 )); further, b j+1 moves down by ε when transforming 1 into bj ∈ δ , however its x-coordinate stays unchanged; this implies that s j is smaller than the slope of b j b j+1 in 1 , hence smaller than α. Since ε ≤ Y2 < dV (1 , b j b j+1 )— given that u 1 lies on u in 1 —it follows that y(b j ) < y(b j+1 ) holds true in δ , hence s j > 0. Thus, s j ∈ (0; α). Property 1. First, the edge uv does not cross or overlap any other edge of G, since no vertex other than u and v lies on or above u in  and δ . Hence, we only need to argue about crossings among edges in the graphs G 1 , . . . , G k . We first deal with . For i = 1, . . . , k, the inductively constructed drawing i of G i is planar, by property 1. Further, for i = 2, . . . , k, the drawing of G i in  is congruent to i , up to affine transformations (a uniform scaling, a rotation, and a translation), which preserve planarity. Moreover, since ε < ε∗ 1 , by Lemma 2.1 we have that the drawing of G 1 in  is planar, as well. It follows that no two edges in the same graph G i cross each other in , for each i = 1, . . . , k. Since  satisfies property 3, the path βuv (G) is represented in  by a curve k monotonically increasing in the x-direction τu i−1 u i (G i ) is also represented in  by a from u to v. Further, the path τ = i=1 curve monotonically increasing in the x-direction from u to v, since it is composed ε ∈ (−α; 0) ∈ of the straight-line segment u 0 u 1 , which has slope − arctan d(1 ,u 0 u1)  π  − 4 ; 0 , given that ε, d(1 , u 0 u 1 ) > 0, that ε < tan(α)·d(1 , u 0 u 1 ), and that α < π4 ,   and of the straight-line segment u 1 u k , which has slope s = α2 ∈ 0; π2 . Hence, for

123

Discrete Comput Geom

i = 1, 2, . . . , k − 1, the vertical line through u i has the drawings of G 1 , . . . , G i to its left and the drawings of G i+1 , . . . , G k to its right in . It follows that no two edges in distinct graphs G i and G j cross in . This proves the planarity of . Since δ and  coincide, except for the position of u, it remains to prove that no edge uu  incident to u with u  = v crosses or overlaps any other edge in δ . Since the vertical line through u 1 has the drawing of G 1 to its left and the drawings of G 2 , . . . , G k to its right in δ , such a crossing might only occur between uu  and another edge ww of G 1 . The proof that uu  and ww  do not cross or overlap is the same as in the proof of Lemma 3.5, with G 1 playing the role of G  and 1 playing the role of   . Property 4. Let x ∈ V (G). If x = u, let Px = (u, v); then the only edge of Px has slope  0 ∈ (−α; α) in δ . If x = u i , for some i ∈ {1, . . . , k − 1}, then let Px = kj=i+1 τu j−1 u j (G j ) and observe that all the edges of Px have slope s = α2 ∈ (−α; α); further Px does not pass through u. If x = u i , for every i ∈ {0, 1, . . . , k}, then x belongs to a unique graph G i , for some i ∈ {1, 2, . . . , k}. We distinguish two cases. i – Assume first that i ≥ 2. Since i satisfies x to  4, there exists a path Px from  property α α u i in G i whose every edge has slope in − 3 ; 3 in i ; then Px consists of Pxi and of  the path kj=i+1 τu j−1 u j (G j ). Since the drawing of G i in δ is congruent to i up to a uniform scaling, a counter-clockwise rotation by s = α2 radians, and a translation,     it follows that every edge of Pxi has slope in s − α3 ; s + α3 = α6 ; 5α 6 ⊂ (−α; α) k in δ ; further, as noted above, all the edges of j=i+1 τu j−1 u j (G j ) have slope s = α2 ∈ (−α; α). Hence, all the edges of Px have slope in (−α; α); finally, Px does not pass through u. – Assume next that i = 1. Refer to Fig. 18. Let τu 0 u 1 (G 1 ) = (u 0 = c1 , c2 , . . . , cr = u 1 ). Since 1 satisfies property 4, there exists a path Px1 = (x = v1 , v2 , . . . , v p = u 1 ) from x to u 1 in G 1 , not passing through u, whose every edge has slope in − α2 ; α2 in 1 ; let h be the smallest index such that vh = c j , for some j ∈ {2, 3, . . . , r }. Such an index h exists (possibly h = p and j = r ). Then let Px consist of the paths (x = v1 , v2 , . . . , vh ), (vh = c j , c j+1 , . . . , cr ), and k / V (Px1 ), we have that u ∈ / V (Px ), hence it suffices j=2 τu j−1 u j (G j ). Since u ∈ to argue about the slopes of the edges of Px in  rather than in δ . • For l = 1, . . . , h − 2, the slope  of vl vl+1 in  is in the interval (−α; α) since it is in the interval − α2 ; α2 ⊂ (−α; α) in 1 and since neither vl nor vl+1 moves when transforming 1 into . • Further, for l =  j, . . . , r − 1, the slope of the edge cl cl+1 in  is ε , which is in the interval (−α; 0) ⊂ (−α; α), given that − arctan d(1 ,u 0 u1) ε, d(1 , u 0 u 1 ) > 0 and that ε < tan(α)· d(1 , u 0 u 1 ). • Moreover, as noted above, the edges of kj=2 τu j−1 u j (G j ) have slope s = α2 ∈ (−α; α). • Finally, let σ1 and σ be the slopes of the edge  vh−1 vh in 1 and , respectively. Since vh−1 vh ∈ E(Px1 ), we have σ1 ∈ − α2 ; α2 ; since α ≤ π4 , we have x(vh−1 ) < x(vh ) in 1 and  (note that the x-coordinates of the vertices do not change when transforming 1 into ). Further, by properties 1–3 of 1 , we have that vh−1 lies below u , which contains vh ; hence, y(vh−1 ) < y(vh ) in

123

Discrete Comput Geom d(Γ1, u 0u 1) u= u 0= c1

u

v= u 4

c2

ε x = v1

cr = u 1

u3 u2

vh = cj

Fig. 18 Illustration for the proof that the slope in δ of every edge in the path Px is in (−α; α), in the case in which x belongs to G 1 . The path Px is thick

1 . Since the vertex vh moves down, while vh−1 stays put, when transforming 1 into , we have that σ < σ1 . Further, since ε ≤ Y2 < dV (1 , vh−1 vh ), we have  α that y(vh−1 ) < y(vh ) in . It follows that σ > 0; hence σ ∈ (0; σ1 ) ∈ 0; 2 ⊂ (−α; α). Property 5. Let x ∈ V (G). If x = v, let Q x = (v, u); then the only edge of Q x has slope π ∈  (π − α; π + α) in δ . If x = u i , for some i ∈ {1, . . . , k − 1}, then let Q x = ij=1 βu j u j−1 (G j ); recall that βu j u j−1 (G j ) has the same vertices as τu j−1 u j (G j ), however in the reverse linear order. Denote the vertices of Q x by (x = w1 , w2 , . . . , wq = u). Consider the edge wl wl+1 , for any 1 ≤ l ≤ q − 1. – If wl wl+1 is in G j , for some j ≥ 2, then its slope in δ is π + s = π + α2 ∈ (π − α; π + α).   ε , – If wl wl+1 is in G 1 and l ≤ q − 2, then its slope in δ is π − arctan d(1 ,u 0 u1) which is in the interval (π −α; π ) ⊂ (π −α; π +α), given that ε, d(1 , u 0 u 1 ) > 0 and that ε < tan(α) · d(1 , u 0 u 1 ).   – Finally, the slope of wq−1 wq in δ is π − arctan δ+d(ε1 ,u 0 u 1 ) , which is in the interval (π − α; π ) ⊂ (π − α; π + α), given that ε, d(1 , u 0 u 1 ) > 0, that δ ≥ 0, and that ε < tan(α) · d(1 , u 0 u 1 ). If x = u i , for every i ∈ {0, 1, . . . , k}, then x belongs to a unique graph G i , for some i ∈ {1, 2, . . . , k}. We distinguish two cases. i – Assume first that i ≥ 2. Since i satisfies property  5, there exists a path Q x from x to u i−1 in G i whose every edge has slope in π − α3 ; π + α3 in i ; then Q x  consists of Q ix and of the path i−1 j=1 βu j u j−1 (G j ); denote the vertices of Q x by (x = w1 , w2 , . . . , wq = u). Consider the edge wl wl+1 , for any 1 ≤ l ≤ q − 1. i • If wl wl+1 it belongs to the path Q x .It followsαthat wl wl+1α has  is inαG i , then α slope in π − 3 ; π + 3 in i , hence it has slope π + s − 3 ; π + s + 3 =   π + α6 ; π + 5α 6 ⊂ (π − α; π + α) in δ . • If wl wl+1 is in G j , for some 2 ≤ j ≤ i − 1, then its slope in δ is π + s = π + α2 ∈ (π − α; π + α).   ε , • If wl wl+1 is in G 1 and l ≤ q − 2, then its slope in δ is π − arctan d(1 ,u 0 u1) . which is in the interval (π − α; π + α), as proven in the case x = u i   • Finally, the slope of wq−1 wq in δ is π − arctan δ+d(ε1 ,u 0 u 1 ) , which is in the interval (π − α; π + α), as proven in the case x = u i .

– Assume next that i = 1. Let τu 0 u 1 (G 1 ) = (u 0 = c1 , c2 , . . . , cr = u 1 ). Since 1 satisfies property 5, there exists a path Q 1x = (x = w1 , w2 , . . . , wq = u) from

123

Discrete Comput Geom

  x to u in G 1 , whose every edge has slope in π − α2 ; π + α2 in 1 . Similarly to the proof that δ satisfies property 5 in Lemma 3.5, we distinguish two cases. If no vertex of Q 1x − {u} belongs to τu 0 u 1 (G 1 ), then let Q x = Q 1x and observe that Q x satisfies the required properties in δ since Q 1x does in 1,δ . Otherwise, let h be the smallest index such that wh = c j , for some j ∈ {2, 3, . . . , r } and define Q x = (x = w1 , w2 , . . . , wh = c j , c j−1 , . . . , c1 = u). • For l = 1, . . . , h − 2, the slope of the edge wl wl+1 is in (π − α; π + α) in δ since it is in (π − α; π + α) in 1,δ . • Further, we argue about the slope s of the edge wh−1 wh in δ . By definition of the index h, the vertices wh−1 and wh are both different from u, hence s coincides with the slope of the edge wh−1 wh in . Let s1 bethe slope of the  edge wh−1 wh in 1 . Since wh−1 wh ∈ Q 1x , we have that s1 ∈ π − α2 ; π + α2 ; since α ≤ π4 , this implies that x(wh−1 ) > x(wh ) in 1 and  (note that the x-coordinates of the vertices do not change when transforming 1 into ). Further, by properties 1–3 of 1 , we have that wh−1 lies below u , which contains wh ; hence, y(wh−1 ) < y(wh ) in 1 . Since the vertex wh moves down, while wh−1 stays put, when transforming 1 into , we have that s > s1 . Further, since ε ≤ Y2 < dV (1 , wh−1 wh ), we have that y(wh−1 ) < y(wh ) in   . It follows that s < π ; hence s ∈ (s1 ; π ) ∈ π − α2 ; π ⊂ (π − α; π + α). • Moreover, for l =  j, j − 1 . . . , 3, the slope of the edge cl cl−1 in δ is π −  ε , which is in the interval (π − α; π + α), as proven in the arctan d(1 ,u 0 u1) case x = u i .   • Finally, the slope of the edge c2 c1 in δ is π − arctan δ+d(ε1 ,u 0 u 1 ) , which is in the interval (π − α; π + α), as proven in the case x = u i . Property 6. Consider any two distinct vertices x, y ∈ V (G). If x and y belong to the same graph G i , for some i ∈ {1, . . . , k}, then there exists a distance-decreasing path Px y from x to y in i , given that i satisfies property 6. If i ∈ {2, . . . , k}, the drawing of G i in δ is congruent to i , up to three affine transformations (a uniform scaling, a rotation, and a translation) which preserve the property of a path to be distance-decreasing; hence Px y is distance-decreasing in δ as well. If i = 1, then the proof that Px y is distance-decreasing in δ is the same as the proof that δ satisfies property 6 in Lemma 3.5, with 1 playing the role of   . We can hence assume that x and y belong to two distinct graphs G i and G j , respectively. – First, suppose that 2 ≤ i < j ≤ k. Let Px y be the path composed  of:  • a path Pxi in G i from x to u i whose every edge has slope in − α3 ; α3 in i ;  j−1 • the path l=i+1 τul−1 ul (G l ); and   • a path Q u j−1 y in G j from u j−1 to y whose every edge has slope in − α3 ; α3 in  j . j

4. Further, The path Pxi exists by induction since i satisfies property  a path Q y in  G j from y to u j−1 whose every edge has slope in π − α3 ; π + α3 in  j exists by induction since  j satisfies property 5, hence Q u j−1 y can be defined as the reverse j

of Q y .

123

Discrete Comput Geom

Since i and  j are counter-clockwise rotated by s = α2 radians in δ , it follows   that every edge of Pxi or Q u j−1 y has slope in α6 ; 5α 6 ; further, every edge of  j−1 α π l=i+1 τu l−1 u l (G l ) has slope s = 2 . Since α ≤ 4 , it follows that Px y is a β-path with β = 0 (see [11] and the proof of Lemma 3.5), hence it is distance-decreasing in δ . – Second, suppose that 2 ≤ j < i ≤ k. Let Px y be the path composed   of: • a path Q ix in G i from x to u i−1 whose every edge has slope in π − α3 ; π + α3 in i ;  i−1 • the path l= j+1 βu l u l−1 (G l ); and   • a path Pu j y in G j from u j to y whose every edge has slope in π − α3 ; π + α3 in  j . j The path Q ix exists by induction since i satisfies  5. Further, a path Py in  property α α G j from y to u j whose every edge has slope in − 3 ; 3 in  j exists by induction j since  j satisfies property 4, hence Pu j y can be defined as the reverse of Py . Since i and  j are counter-clockwise rotated by s = α2 radians in δ , it follows   ; further, every edge of that every edge of Q ix or Pu j y has slope in π + α6 ; π + 5α 6 i−1 α π l= j+1 βu l u l−1 (G l ) has slope π + 2 . Since α ≤ 4 , it follows that Px y is a β-path with β = π , hence it is distance-decreasing in δ . – Third, suppose that i = 1 and j > 1. Then let Px y be the path composed of: • a path Px1 in G 1 from x to u 1 whose every edge has slope in (−α; α) in δ , where Px1 does not pass through u, unless x = u;  j−1 • the path l=2 τul−1 ul (G l ); and   • a path Pu j−1 y in G j from u j−1 to y whose every edge has slope in − α3 ; α3 in j. The path Pu j−1 y can be proven to exist as in the case in which 2 ≤ i < j ≤ k. We prove that a path Px1 satisfying the above properties exists. Let Px1 = τu 0 u 1 (G 1 ). τu 0 u 1 (G 1 ) = (u 0 = c1 , c2 , . . . , cr = u 1 ). If x = u, then  let ε 1 Every edge of Px other than c1 c2 has slope − arctan d(1 ,u 0 u 1 ) in δ , while   c1 c2 has slope − arctan δ+d(ε1 ,u 0 u 1 ) . These slopes are smaller than 0, given that ε, d(1 , u 0 u 1 ) > 0 and δ ≥ 0, and larger than −α, given that δ ≥ 0 and ε < tan α · d(1 , u 0 u 1 ). Thus, every edge of Px1 has slope in (−α; α) in δ . If x = u, then Px1 can be shown to exist as in the proof that δ satisfies property 4, by considering a path (x = v1 , v2 , . . . , vp = u 1) in G 1 that does not pass through u and whose every edge has slope in − α2 ; α2 in 1 and by defining Px1 = (v1 , v2 , . . . , vh = c j , c j+1 , . . . , cr ), where h is the smallest index such that vh ∈ V (τu 0 u 1 (G 1 )). This concludes the proof that a path Px1 satisfying the required / V (Px1 ), properties exists. Note that u ∈ / V (Px y ), unless x = u, given that u ∈ unless x = u. Since  j is counter-clockwise rotated by s = α2 radians in δ , it follows that every   1 edge of Pu j−1 y has slope in α6 ; 5α 6 ; further, every edge of Px has slope in (−α; α)

123

Discrete Comput Geom

u

δ u= b1

dH (Γδ , y y 1) y 1= bm dV (Γδ , y y 1) ΓH y b2 φ 2

β

v hβ ρ Dρ

Fig. 19 The straight-line drawing  of G in Case B. For the sake of readability, φ and ρ are larger than they should be

 j−1 and every edge of l=2 τul−1 ul (G l ) has slope s = α2 . Since α ≤ π4 , it follows that Px y is a β-path with β = 0, hence it is distance-decreasing in δ . – Finally, suppose that i > 1 and j = 1. Let Px y be the path composed   of: • a path Q xu i−1 in G i from x to u i−1 whose every edge has slope in π − α3 ; π + α3 in i ;  i−1 • the path l=2 βul ul−1 (G l ); and • a path Pu 1 y in G 1 from u 1 to y whose every edge has slope in (π − α; π + α) in δ , where Pu 1 y does not pass through u, unless y = u. The path Q xu i−1 can be proven to exist as in the case in which 2 ≤ j < i ≤ k. We prove that a path Pu 1 y with the above properties exists. Let βu 1 u 0 (G 1 ) = (u 1 = cr , cr −1 , . . . , c1 = u 0 ). If y = u, then let  Pu 1εy = βu 1 u 0 (G 1 ). Every in δ , while c2 c1 edge of Pu 1 y other than c2 c1 has slope π − arctan d(1 ,u 0 u1)   ε has slope π − arctan δ+d(1 ,u 0 u 1 ) . These slopes are smaller than π , given that ε, d(1 , u 0 u 1 ) > 0 and δ ≥ 0, and larger than π − α, given that δ ≥ 0 and ε < tan α · d(1 , u 0 u 1 ). Thus, every edge of Pu 1 y has slope in (π − α; π + α) in δ . If y = u, then Pu 1 y can be shown to exist as follows. A path Py1 from y to u 1 whose every edge has slope in (−α; α) in δ and which does not pass through u can be shown to exist as in the proof that δ satisfies property 4; then Pu 1 y is the reverse of Py1 . This concludes the proof that a path Pu 1 y satisfying the required properties exists. Since  j is counter-clockwise rotated by s = α2 radians in δ , it follows that every   ; further, every edge of Pu 1 y has slope edge of Q xu i−1 has slope in π + α6 ; π + 5α 6 i−1 in (π − α; π + α) and every edge of l=2 βul ul−1 (G l ) has slope π + α2 . Since α ≤ π4 , it follows that Px y is a β-path with β = π , hence it is distance-decreasing  in δ . Hence δ satisfies property 6. This concludes the proof of the lemma.

We now discuss Case B, in which (G, u, v) is decomposed according to Lemma 3.3. Refer to Figs. 19–21. First, the triple (H, u, y1 ) is a strong circuit graph; further, |V (H )| ≥ 3, hence H is not a single edge. Apply induction in order to construct a straight-line drawing  H of H with α2 as a parameter. Let βuy1 (H ) = (u = b1 , b2 , . . . , bm = y1 ). Let φi be the slope of the edge bi bi+1 in  H and let φ = mini=2,...,m−1 {φi }. By property (c) of the strong circuit graph (H, u, y1 )—see Definition 3.1—if the edge uy1 belongs to H then it coincides with  τuy1 (H ). Hence, m ≥ 3 and φ is well-defined. Further, φ is in the interval the path 0; α2 by property 3 of  H .

123

Discrete Comput Geom Fig. 20 Illustration for the notation of Case B

u

Y

pρ,u v

dy 1 v

y1

ΓH

pρ,β ρ

d∗

Dρ

y (a)

(b)

pρ,β

pρ,u

u1 u0

Γ1

u2 Γ2 Dρ

u1

v= u k Γ3 Γ1,d∗

u2 Γ2

v= u k Γ3

Dρ

Fig. 21 A closer look at Dρ . Figure (a) represents the drawings 1 , . . . , k , once they have been uniformly scaled, rotated, and translated, while (b) also has the vertex u 0 moved by d ∗ units (this movement actually happens before the rotation and translation of 1 )

   H ,y y1 ) . Note Recall that y = y1 and let β = 21 min φ, arctan 3dV ( H ,ydV y( 1 )+3d H ( H ,y y1 ) that β > 0, given that φ, dV ( H , y y1 ) > 0 and d H ( H , y y1 ) ≥ 0. In particular, dV ( H , y y1 ) > 0 because y1 is a vertex of τuy1 (H ) and y is an internal vertex of βuy1 (H ) by Lemma 3.3, and because of properties 1–3 of  H . Also note that β < α4 ,   given that φ < α2 . Hence, β is in the interval 0; α4 . Consider a half-line h β with slope β starting at y . Place the vertex v at the intersection point between h β and the horizontal line u through u. Draw all the trivial (H ∪ {v})-bridges of G as straight-line segments. This concludes the construction if every (H ∪ {v})-bridge of G is trivial. Otherwise, B is the only non-trivial (H ∪ {v})bridge of G. Then B consists of k strong circuit graphs (G i , u i−1 , u i ), where u 0 = y and u k = v. With a slight change of notation, in the remainder of the section we assume that, if the edge y v exists, then it is an edge of B (rather than an individual trivial (H ∪ {v})-bridge B−1 of G); in this case (B , u 0 , u k ) is a strong circuit graph (this is proven in the proof of Lemma 3.3, where the graph B together with the edge y v was denoted by B ). We claim that v lies to the right of y1 . The polygonal line representing β y y1 (H ) in  H and the straight-line segment y v are both incident to y . By definition of φ and since  H satisfies property  3, β y y1 (H ) is composed of straight-line segments  with slopes in the range φ; α2 , while y v has slope β. The claim then follows from 0 < β < φ < π2 . We introduce some notation. Refer to Fig. 20. Denote by d y1 v the distance between y1 and v. Let Y > 0 be the minimum distance in  H of any vertex strictly below u  d from u . Let ρ = min y31 v , Y2 . Let Dρ be the disk with radius ρ centered at v. Let pρ,β be the intersection point closer to y of the boundary of Dρ with h β . Let pρ,u be the intersection point closer to y1 of the boundary of Dρ with u . Finally, let d ∗ be the Euclidean distance between y and pρ,β .     Let α  = β2 . Since β is in the interval 0; α4 , we have that α  is in the interval 0; α8 . For i = 1, . . . , k, apply induction in order to construct a straight-line drawing i of

123

Discrete Comput Geom

G i with α  as a parameter (if G i is a single edge, then the parameter does not matter). Uniformly scale the drawings 1 , . . . , k so that the Euclidean distance between u i−1 and u i is equal to ρk . Move the vertex u 0 in 1 by d ∗ units to the left, obtaining a drawing 1,d ∗ . Rotate the drawings 1,d ∗ , 2 , . . . , k counter-clockwise by β radians. Translate 1,d ∗ , 2 , . . . , k so that, for i = 1, . . . , k − 1, the representations of u i in i and i+1 (in 1,d ∗ and 2 if i = 1) coincide and so that the representation of u 0 in the scaled and rotated drawing 1,d ∗ coincides with the one of y in  H . This completes the construction of a straight-line drawing  of G. Before proving that the drawing δ —for any δ ≥ 0—satisfies properties 1–6 of Theorem 3.4, we give a few comments on the construction. By construction, the vertex v is placed on the same horizontal line as the path τuy1 (G), to the right of y1 ; this immediately ensures property 2 for δ . Property 3 is also easy to establish. Indeed, by induction the edges of βuy (G) have the desired slope in δ , as they all belong to H , whosedrawing  is inductively constructed. Further, the slopes of the edges of β y v (G) are in − α3 ; α3 in the inductively constructed drawings of G 1 , . . . , G k ; after the rotation of the drawings of G 1 , . . . , G k by β = α2 radians,   these edges have slopes in α6 ; 5α 6 , which is a sub-interval of the desired interval (0; α). The drawings of G 1 , . . . , G k are “very flat”, as they are inductively constructed with parameter α3 ; further, the paths τu 0 u 1 (G 1 ), . . . , τu k−1 u k (G k ) all lie on the same line h. These two facts imply that the drawings of G 1 , . . . , G k in δ do not cross each other and that one can construct distance-decreasing paths in δ between any two vertices in G 1 , . . . , G k by suitably combining paths satisfying properties k 4 and 5 in τul−1 ul (G l ) the individual drawings of G 1 , . . . , G k , together with sub-paths of l=1 k and l=1 βul ul−1 (G l ), similarly to Case A with k ≥ 2. The vertex v is “very far” from the drawing of H in δ , while the drawings of G 1 , . . . , G k in δ are “very close” to v. These two facts have several consequences. First, the drawing of H does not cross the drawings of G 1 , . . . , G k in δ , hence δ satisfies property 1. Second, consider a path satisfying property 4 in the drawing of H in δ and connecting a vertex x of H to y1 ; every edge of this path, when traversed towards y1 , gets you closer to every vertex of G 1 , . . . , G k , except possibly for u 0 . Similarly, a path satisfying property 5 in the drawing of G i , combined with consider i−1 βul ul−1 (G l ); every edge of this path, when traversed towards u 0 , gets you the path l=1 closer to every vertex of H . These are the fundamental observations that are needed to establish properties 4–6 for δ . A major complication stems from the fact that the vertex y = u 0 is shared by H and G 1 . This implies that not the entire drawing of G 1 can be “very close” to v in δ , but one of its vertices, namely u 0 , has to be pulled “far apart” from the rest of the drawing of G 1 . This is where we use the property that, in our drawing  of a strong circuit graph (G, u, v), the vertex u can be moved by an arbitrary amount to the left without violating properties 1–6; note that, in the previous inductive cases, we guaranteed this property, however we did not use it yet. We now prove the following. Lemma 3.7 For any δ ≥ 0, the drawing δ constructed in Case B satisfies properties 1–6 of Theorem 3.4.

123

Discrete Comput Geom Fig. 22 The drawing  j and the disk D j centered at u j with radius d( j , u j−1 u j )

uj − 1

π 3

Γj

π 3

uj

Dj π 3

Proof Let  H,δ be the drawing obtained from  H by moving u by δ units to the left. Property 2. By Lemma 3.3, we have that τuv (G) = τuy1 (H ) ∪ y1 v. By property 2 of  H,δ , we have that τuy1 (H ) lies entirely on u with y1 to the right of u. By construction v also lies on u . As proven before the lemma’s statement, v lies to the right of y1 . This implies property 2 for δ . Property 3. By Lemma 3.3, we have that βuv (G) = βuy (H ) ∪ βu 0 u 1 (G 1 ) ∪  = v). The slope βu 1 u 2 (G 2 ) ∪ · · · ∪ βu k−1 u k (G k ). Let βuv (G) = (u = b1 , b2 , . . . , bm   of the edge b1 b2 in δ is equal to its slope in  H,δ ; this is because the drawing of H in δ coincides with  H,δ and because b2 is a vertex of H , given  that y = u since y is an internal vertex of βuv (G) . Hence the slope of b1 b2 is in − α2 ; 0 ⊂ (−α; 0) in δ since  H,δ satisfies property 3. We now argue about the slope s j of the edge bj bj+1 in δ , for any j = 2, . . . , m − 1. – If bj bj+1 is an edge of βuy (H ), then its slope in δ is equal to its slope in  H,δ ,   since the drawing of H in δ coincides with  H,δ . Thus, s j ∈ 0; α2 ⊂ (0; α), since  H,δ satisfies property 3. – If bj bj+1 coincides with a graph G i , then s j = β. Since 0 < β < α4 , we have s j ∈ (0; α). – If bj bj+1 belongs to a graph G i , for some i ∈ {1, . . . , k}, with |V (G i )| ≥ 3, and with bj = u i−1 (the latter condition implies that bj bj+1 is not the first edge of βu i−1 u i (G i )), then s j is given by the slope bj bj+1 has in i , which is in (0; α  ) by property 3 of i , plus β, which results from the rotation of i . Hence s j ∈ (β; β + α  ); since β > 0, β < α4 , and α  < α8 , we have that s j ∈ (0; α). – If bj bj+1 belongs to a graph G i , for some i ∈ {2, . . . , k}, with |V (G i )| ≥ 3, and with bj = u i−1 (the latter condition implies that bj bj+1 is the first edge of βu i−1 u i (G i )), then s j is given by the slope bj bj+1 has in i , which is in (−α  ; 0) by property 3 of i , plus β, which results from the rotation of i . Hence s j ∈ (β − α  ; β). Since α  ≤ β2 < β < α4 < α, we have that s j ∈ (0; α). – Finally, assume that bj bj+1 belongs to G 1 , that |V (G 1 )| ≥ 3, and that bj = u 0 . Then s j is given by the slope bj bj+1 has in 1,d ∗ , which is in (−α  ; 0) by property 3 of 1,d ∗ , plus β, which results from the rotation of 1,d ∗ . Hence s j ∈ (β −α  ; β) ⊂ (0; α). Property 1. Before proving property 1, we prove the following useful statement: Every vertex z = u 0 that belongs to a graph G i , for any i ∈ {1, . . . , k}, lies inside the disk Dρ in δ . Note that this statement shows a sharp geometric separation between the

123

Discrete Comput Geom

vertices that are in H and those that are not. Refer to Fig. 22. Consider the drawing  j , for any j ∈ {1, . . . , k} (note that 1 is considered before moving u 0 by d ∗ units to the left) and consider the disk D j centered at u j with radius d( j , u j−1 u j ). By properties 1 and 2 of  j , the path τu j−1 u j (G j ) lies on the straight-line segment u j−1 u j in  j , hence it lies inside D j . Further, all the edges of βu j−1 u j (G j ) have   π π    slope in (−α  ; α  ) ⊂ − α8 ; α8 ⊂ − 32 ; 32 ⊂ − π3 ; π3 ; hence βu j−1 u j (G j ) also lies inside D j . By property 1 of  j , the entire drawing  j lies inside D j . Hence, u j−1 is the farthest vertex of G j from u j in  j . This property holds true also after the drawings 1 , . . . , k are uniformly scaled; further, after the scaling, the distance between u j−1 and u j is ρk , by construction. By the triangular inequality, we have k ρ that d(δ , vz) ≤ j=i+1 d(δ , u j−1 u j ) + d(δ , u i z). Since d(δ , u j−1 u j ) = k ρ for any j ∈ {2, . . . , k}, and since d(δ , u i z) ≤ k (this exploits z = u 0 and hence d(δ , u i z) = d(i , u i z), where i is understood as already scaled), we have that ≤ ρ. Thus z lies inside Dρ . d(δ , vz) ≤ (k−i+1)ρ k We now discuss the possible overlaps or crossings that might occur in δ . – H against H: The drawing of H in δ coincides with  H,δ , hence it is planar since  H,δ satisfies property 1 by induction. – Gi against Gi : The drawings of G 1 , G 2 , . . . , G k in δ are planar since they coincide with 1,d ∗ , 2 , . . . , k , which satisfy property 1 by induction. – Gi against Gj : Since δ satisfies property 3, the path β y v (G) is represented in δ by a curve monotonically increasing in the x-direction from y to v. Further, the k path τ =  i=1 i) is represented in δ by a straight-line segment with τu i−1u i (G π ; thus, τ is also represented by a curve monotonically slope β ∈ 0; α4 ⊂ 0; 16 increasing in the x-direction from y to v. Hence, for i = 1, . . . , k − 1, the vertical line through u i has the drawings of G 1 , . . . , G i to its left and the drawings of G i+1 , . . . , G k to its right in δ . It follows that no two edges or vertices belonging to distinct graphs G i and G j cross or overlap in δ . – H against B against B1 , . . ., B−1 : First, consider the vertical line 1 through y1 . By properties 1–3 of  H,δ , the line 1 has  H,δ to its left, except for the vertex y1 which is on 1 . Further, since ρ < d y1 v , the disk Dρ lies to the right of 1 . Since all the vertices of B different from u 0 lie inside Dρ , it follows that: (i) no edge or vertex in H overlaps a vertex of B ; and (ii) no edge or vertex in H crosses or overlaps an edge of B , unless the latter is incident to u 0 . Note that every vertex of G is in H or in B ; further, every edge of G belongs to H , or belongs to B , or is a trivial (H ∪ {v})-bridge Bi of G (hence it is incident to v and to a vertex yi of βuy1 (H )). Thus, it only remains to show the following: • statement (a): no trivial (H ∪ {v})-bridge of G crosses or overlaps any edge or vertex of B or any distinct trivial (H ∪ {v})-bridge of G in δ ; • statement (b): no trivial (H ∪ {v})-bridge of G crosses or overlaps any edge or vertex of H in δ ; and • statement (c): no edge of B incident to u 0 crosses or overlaps any edge or vertex of H in δ . Recall that βuy1 (H ) = (u = b1 , b2 , . . . , bm = y1 ). Let y = b j , where j ∈ {2, 3, . . . , m − 1}.

123

Discrete Comput Geom y 1= bm

Fig. 23 Illustration for the proof of the bridge-slope statement

v

bi+1 bi b2

y = bj

=β

≤β

≥φ

≤β

We first prove the following bridge-slope statement: The straight-line segments b j v, b j+1 v, . . . , bm v have slopes in decreasing order in the interval [0; β] in δ . Note that these straight-line segments do not necessarily correspond to edges of G. Refer to Fig. 23. First, the slope of b j v is β, by construction; also, the slope of bm v is 0, by construction. Now assume, by induction, that b j v, b j+1 v, . . . , bi v, bm v have slopes in decreasing order in the interval [0; β] in δ , for some i ∈ { j, j + 1, . . . , m − 2}. We prove that the same property is true for b j v, b j+1 v, . . . , bi v, bi+1 v, bm v. Since  H,δ satisfies properties 1–3, the vertices b2 , . . . , bm−1 have x- and y-coordinate smaller than bm = y1 and hence smaller than v. It follows that the slope of bi+1 v is larger than 0. The edge bi bi+1  has slope in φ; α2 , by definition of φ and since  H,δ satisfies property 3. Since β < φ and since, by the inductive hypothesis, the slope of bi v is at most β, the edge bi bi+1 lies above the line through bi and v. Hence, bi+1 v has slope smaller than the one of bi v, hence b j v, b j+1 v, . . . , bi v, bi+1 v, bm v have slopes in decreasing order in the interval [0; β] in δ . This completes the induction and hence proves the bridge-slope statement. The bridge-slope statement trivially implies that no two trivial (H ∪ {v})-bridges of G overlap. This proves statement (a) if every (H ∪ {v})-bridge of G is trivial. Otherwise, G contains a non-trivial (H ∪ {v})-bridge B , which consists of the graphs G 1 , . . . , G k . The bridge-slope statement implies that all the trivial (H ∪ {v})-bridges B1 , . . . , B−1 of G lie above the line h β (recall that, if the edge y v exists, then it is an edge of B and B = G 1 ), except at v. On the other hand, the drawing of B lies on or below h β , given that the drawings 1,d ∗ , 2 , . . . , k of G 1 , G 2 , . . . , G k satisfy properties 1–3 and are rotated so that k τ = i=1 τu i−1 u i (G i ) lies on h β . This implies that none of B1 , . . . , B−1 crosses or overlaps any edge or vertex of B , and hence proves statement (a). In order to prove statement (b), consider the infinite closed strip S delimited by the horizontal lines through b2 and bm . The path βb2 bm (H ) splits S into two regions Sl and Sr to the left and to the right of βb2 bm (H ), respectively. properties 1–3 of  H,δ imply that H lies entirely in Sl . On the other hand, B1 , . . . , B−1 lie in Sr ; this is because the edges of the path βb2 bm (H ) have slopes in φ; α2 , by definition of φ and by property 3 of  H,δ , and because the segments b j v, b j+1 v, . . . , bm v (including the trivial (H ∪ {v})-bridges of G) have slopes in [0; β], by the bridgeslope statement, where β < φ. Thus, no trivial (H ∪ {v})-bridge of G crosses or overlaps any vertex or edge of H in δ , which proves statement (b). The proof of statement (c) is similar to the one of statement (b). In particular, properties 1–3 of 1,d ∗ imply that the edges of B incident to u 0 have slope in the interval (0; β] in δ , hence they all lie to the right of βb2 bm (H ), whose edges have

123

Discrete Comput Geom

  slopes in φ; α2 , given that β < φ. Since all the vertices and edges of H lie in Sl , statement (c) follows. This concludes the proof of property 1 for δ . Property 4. Let x ∈ V (G). – Assume first that x ∈ V (H ). Since the drawing of H in δ coincides with  H,δ , there exists a path Px in H from x to y1, not passing through u unless x = u, and whose every edge has slope in − α2 ; α2 ⊂ (−α; α) in δ . Further, the edge y1 v has slope 0. Hence, the path Px = Px ∪ y1 v satisfies the required properties. – If x ∈ / V (H ), then x ∈ V (G i ), for some i ∈ {1, . . . , k}. If i ≥ 2, then the path Px consists of a path Px from x to u i in G i whose every edge has slope   of the path in k(−α ; α ) in i —this path exists since i satisfies property 4—and  from x to u in τ (G ). If i = 1, then the path P consists of a path P j x 1 x j=i+1 u j−1 u j G 1 whose every edge has slope in (−α  ; α  ) in 1,d ∗ —this path exists since 1,d ∗  satisfies property 4—and of the path kj=2 τu j−1 u j (G j ). Since 1,d ∗ , 2 , . . . , k are rotated by β radians in δ , the edges of Px have slopes in the range (β − α  ; β + α  ) in δ . Since α  = β2 and 0 < β < α4 , we have that (β − α  ; β + α  ) ⊂  3α  0; 8 ⊂ (−α; α). Further, every edge in τu j−1 u j (G j ) has slope 0 in  j and hence  β in δ . Since 0 < β < α4 , we have that every edge in kj=i+1 τu j−1 u j (G j ) has slope in (−α; α). Note that Px does not pass through u, since u does not belong to any graph among G 1 , . . . , G k . Thus, Px satisfies the required properties. Property 5. Let x ∈ V (G). – Assume first that x ∈ V (H ). Since the drawing of H in δ coincides with  H,δ and since  H,δ satisfies property 5, there exists a path Q x from x to u whose every  edge has slope in π − α2 ; π + α2 ⊂ (π − α; π + α). Thus, the path Q x = Q x satisfies the required properties. – If x ∈ / V (H ), then x ∈ V (G i ), for some i ∈ {1, . . . , k}. Then the path Q x consists of three paths. • First, Q x contains a path Q x from x to u i−1 in G i whose every edge has slope in (π − α  ; π + α  ) in i , if i ≥ 2, or in 1,d ∗ , if i = 1. This path exists since 1,d ∗ , 2 , . . . , k satisfy property 5. Since 1,d ∗ , 2 , . . . , k are rotated by β radians in δ , the edges of Q x have slopes in the range (π +β −α  ; π +β +α  ). Since α  = β2 and 0 < β < α4 , we have that (π + β − α  ; π + β + α  ) ⊂   π ; π + 3α 8 ⊂ (π − α; π + α).  • Second, Q x contains the path i−1 j=1 βu j u j−1 (G j ); by properties 1 and 2, every edge in βu j u j−1 (G j ) has slope π in  j , if j ≥ 2, or in 1,d ∗ , if j = 1, hence it has slope π + β in δ . Since 0 < β < α4 , we have that every edge in the path i−1 j=1 βu j u j−1 (G j ) has slope in (π − α; π + α). • Third, Q x contains a path Q y from u 0 = y to u in H whose every edge has   slope in π − α2 ; π + α2 ⊂ (π − α; π + α); this path exists since the drawing of H in δ coincides with  H,δ and since  H,δ satisfies property 5. Thus, the path Q x satisfies the required properties. Property 6. Consider any two vertices x, y ∈ V (G). We prove the existence of a path Px y from x to y in G which does not pass through u, unless x = u or y = u,

123

Discrete Comput Geom

and which is distance-decreasing in δ . We distinguish several cases, based on which graphs among H, G 1 , . . . , G k the vertices x and y belong to. – Suppose first that x and y belong to H . Since  H,δ satisfies property 6, there exists a path Px y from x to y in H which does not pass through u, unless x = u or y = u, and which is distance-decreasing in  H,δ . Since the drawing of H in δ coincides with  H,δ , it follows that Px y is distance-decreasing in δ ; further, Px y does not pass through u, unless x = u or y = u. – Suppose next that x and y belong to the same graph G i , for some i ∈ {1, 2, . . . , k}. Since the drawings 1,d ∗ , 2 , . . . , k satisfy property 6, there exists a path Px y from x to y in G i that is distance-decreasing in i , if i ≥ 2, or in 1,d ∗ , if i = 1. Since the drawing of G i in δ is congruent to i , if i ≥ 2, or to 1,d ∗ , if i = 1, up to three affine transformations, namely a uniform scaling, a rotation, and a translation, that preserve the property of a path to be distance-decreasing, it follows that Px y is distance-decreasing in δ . Note that u ∈ / V (Px y ). – Suppose now that x belongs to a graph G i and y belongs to a graph G j for some 1 ≤ i < j ≤ k. Then (similarly to the case in which x ∈ V (G i ), y ∈ V (G j ), and 2 ≤ i < j ≤ k in Lemma 3.6) let Px y be the path composed of a path Pxi in G i from  j−1 x to u i whose every slope in i is in (−α  ; α  ), of the path l=i+1 τul−1 ul (G l ), and of a path Q u j−1 y from u j−1 to y in G j whose every edge has slope in (−α  ; α  ) in  j . The path Pxi exists since 1,d ∗ , 2 , . . . , k satisfy property 4. The path Q u j−1 y j

can be defined as the reverse of a path Q y from y to u j−1 whose every edge has j slope in (π − α  ; π + α  ) in  j ; the path Q y exists since  j satisfies property 5. Since i and  j are counter-clockwise rotated by β radians in δ , it follows that every edge of Pxi or Q u j−1 y has slope in (β − α  ; β + α  ); further, every edge of  j−1 α α π  l=i+1 τu l−1 u l (G l ) has slope β. Since 0 < β ≤ 4 , 0 < α ≤ 8 , and 0 < α ≤ 4 it follows that Px y is a γ -path with γ = 0 (see [11] and the proof of Lemma 3.5), hence it is distance-decreasing in δ . – The case in which 1 ≤ j < i ≤ k is symmetric to the previous one and analogous to the case in which x ∈ V (G i ), y ∈ V (G j ), and 2 ≤ j < i ≤ k in Lemma 3.6. – Suppose now that x belongs to H and y belongs to a graph G i , for some i ∈ {1, . . . , k}. If i = 1 and y = u 0 , then y ∈ V (H ) and Px y is defined as discussed above. Assume hence that y = u 0 . Then the path Px y consists of three sub-paths. • The first sub-path of Px y is a path Px in H from x to y1 . Suppose first that x = u. Then let Px = τuy1 (H ). Let Px = (x = z 1 , z 2 , . . . , z s = y1 ); we prove that d(δ , z h y) > d(δ , z h+1 y) holds true for any h = 1, . . . , s − 1. Consider the vertical line 1 through y1 , oriented towards increasing y-coordinates. As argued above, every vertex of G 1 , . . . , G k different from u 0 lies inside Dρ ; in particular, y lies inside Dρ . Further, the disk Dρ is to the right of 1 ; this is because the center of Dρ (that is, the vertex v) is on the same horizontal line u as y1 , the horizontal distance between y1 and v is d y1 v , and the radius of Dρ is smaller than d y1 v (it is, in fact, at d

most y31 v ). By properties 1 and 2 of δ , the edge z h z h+1 is horizontal, with z h to the left of z h+1 . Hence, the line h orthogonal to z h z h+1 and passing through its midpoint is also vertical and has 1 to its right. It follows that

123

Discrete Comput Geom

y is to the right of h . Since the half-plane to the right of h represents the locus of the points of the plane that are closer to z h+1 than to z h , we have d(δ , z h y) > d(δ , z h+1 y). Suppose next that x = u. By property 4 of  H,δ , there exists a path Px = (x = z 1 , z 2 , . . . , z s = y1 ) in H that connects  x toy1 , that does not pass through u, and whose every edge has slope in − α2 ; α2 in  H,δ . We prove that, for any h = 1, 2, . . . , s − 1, d(δ , z h y) > d(δ , z h+1 y); refer to Fig. 24. Since of H in δ coincides with  H,δ , the edge   the drawing z h z h+1 has slope in − α2 ; α2 in δ . Consider the line h that passes through y1 , that is directed towards increasing y-coordinates and that is orthogonal to the   π +α ; line through z h and z h+1 . Denote by sh the slope of h . Then sh ∈ π −α 2 2 . We prove that h has the disk Dρ to its right. In order to do that, consider the point pT on the half-line with slope π −α 2 starting at y1 and such that dV (δ , y1 pT ) = ρ. Further, consider the point p B on the half-line with slope −π +α starting at y1 and such that dV (δ , y1 p B ) = ρ. Note that pT p B is a 2 vertical straight-line segment with length 2ρ. Consider the infinite closed strip S with height 2ρ that is delimited by the horizontal lines through pT and p B . Since Dρ has its center on u and has radius ρ, it  lies inside  S. The part of h π +α inside S is to the left of pT p B , given that sh ∈ π −α ; 2 2 . Hence, we only need to show that pρ,u , which is the point of Dρ with smallest x-coordinate, lies to the right of pT pB . We have that d(δ , y1 pρ,u ) = d y1 v −  ρ. Further, d H (δ , y1 pT ) = ρ · tan α2 . Hence, it suffices to prove ρ · tan α2 < d y1 v − ρ, α d y1 v d y1 v that is ρ < 1+tan( α ; this holds true since ρ < 3 and tan 2 < 1, given that 2) 0 < α < π4 . The line h has the drawing of H (and in particular the midpoint of the edge z h z h+1 ) to its left in δ ; this comes from Lemma 2.2, applied to H , with u = y1 , with the paths delimiting the graph being τ y1 u (H ) (whose every edge has slope at least sm = π − α2 and at most s M = π + α2 , by property 3 of  H,δ ) and β y1 u (H ) (whose every edge has slope π , which is larger than sm and smaller than s M ), with 2 = h , and with 1 and 3 being the lines with slopes π2 − α and π2 + α, respectively, through y1 , oriented towards increasing y-coordinates. Note that the slopes s1 , s2 , and s3 of 1 , 2 , and 3 , respectively, satisfy 0 < s1 ≤ s2 ≤ s3 < π and s3 = π2 + α < sm = π − α2 < s M = π π + α2 < s1 + π = 3π 2 − α, given that α < 4 .  Now consider the line h parallel to h , passing through the midpoint of the edge z h z h+1 , and oriented towards increasing y-coordinates; h has h to its right, given that the midpoint of z h z h+1 is to the left of h in δ . Thus, h has Dρ , and in particular y, to its right. Since the half-plane to the right of h represents the locus of the points of the plane that are closer to z h+1 than to z h , it follows that d(δ , z h y) > d(δ , z h+1 y). • The second sub-path is the edge y1 v. Since y lies in Dρ , we have that d y1 v 3 . By the triangular inequality, we have that d(δ , y1 y) > 2d d(δ , y1 v) − d(δ , vy) ≥ d y1 v − ρ ≥ 3y1 v . Hence, d(δ , y1 y) > d(δ , vy). k The third sub-path is a path Pvy that connects v to y, that belongs to l=i Gl , and that is distance-decreasing in δ . The existence of this path can be proven

d(δ , vy) ≤ ρ ≤

•

123

Discrete Comput Geom Fig. 24 Illustration for the proof that d(δ , z h y) > d(δ , z h+1 y) if z h z h+1 is in Px . For the sake of readability, Dρ is larger than it should be

h h

π− α 2

pT α 2 u

z h z h+1

Dρ

ρ pρ,u

y1 α 2

ρ

v y

pB − π+ α 2

as in the case in which x and y belong to the same graph G i or belong to two graphs G i and G j , respectively, for some 1 ≤ j < i ≤ k. – Suppose finally that x belongs to G i , for some i ∈ {1, . . . , k}, and y belongs to H . If i = 1 and x = u 0 , then x ∈ V (H ) and Px y is defined as discussed above. Assume hence that x = u 0 . We now describe the path Px y , which consists of three sub-paths. • The first sub-path of Px y is a path Q x in G i from x to u i−1 whose every edge has slope in (π − α  ; π + α  ) in i , if i ≥ 2, or in 1,d ∗ , if i = 1. This path exists since 1,d ∗ , 2 , . . . , k satisfy property 5. The second sub-path of  Px y is i−1 j=1 βu j u j−1 (G j ). Since 1,d ∗ , 2 , . . . , k satisfy properties 1 and 2,  every edge in i−1 j=1 βu j u j−1 (G j ) has slope π in 1,d ∗ , 2 , . . . , k . Let (x = z 1 , z 2 , . . . , z s−1 , z s = y = u 0 ) be the union of these two sub-paths of Px y . We prove that d(δ , z h y) > d(δ , z h+1 y), for any h ∈ {1, 2, . . . , s −1}. Since the drawings 1,d ∗ , 2 , . . . , k are counter-clockwise rotated by β radians in δ , it follows that z h z h+1 has slope in the interval (π + β − α  ; π + β + α  ) in δ . We first argue about the case in which h ∈ {1, 2, . . . , s − 2}; we will later deal with the case in which h = s − 1. Note that z h and z h+1 lie in Dρ in δ , given that z h , z h+1 = y . Consider the line h that passes through y1 , that is directed towards increasing y-coordinates and that is orthogonal to the line through zh  and z h+1 . Denote by sh the slope of h . Then sh ∈ π2 + β − α  ; π2 + β + α  . Similarly to the case in which x ∈ V (H ) and y ∈ V (G i ), we have that h has the disk Dρ to its right and the drawing of H to its left (the main difference is that the gray angles in Fig. 24 are now β + α  rather than α2 ). We now present proofs for these statements. * We prove that h has Dρ to its right. Let pT ( p B ) be the point on the half-line with slope π2 − β − α  (resp. − π2 + β + α  ) starting at y1 and such that dV (δ , y1 pT ) = ρ (resp. dV (δ , y1 p B ) = ρ). Then pT p B is a vertical straight-line segment with length 2ρ and Dρ lies inside the infinite closed strip S with height 2ρ that is delimited by the horizontal lines through pT and p B . The part of h inside S is to the left of pT p B , since sh ∈ π2 + β − α  ; π2 + β + α  . Hence, we only need to show that pρ,u lies to the right of pT p B . We have d(δ , y1 pρ,u ) = d y1 v − ρ, while d H (δ , y1 pT ) = ρ · tan(β + α  ). Hence, it suffices to prove that

123

Discrete Comput Geom d

d

y1 v y1 v  ρ < 1+tan(β+α  ) ; this holds true since ρ < 3 and tan(β + α ) < 1, π π and 0 < α  < α8 < 32 . given that 0 < β < α4 < 16 * The line h has the drawing of H (and in particular y) to its left in δ ; this comes from Lemma 2.2, applied to H , with u = y1 , with the paths delimiting the graph being τ y1 u (H ) (whose every edge has slope at least sm = π − α2 and at most s M = π + α2 , by property 3 of  H,δ ) and β y1 u (H ) (whose every edge has slope π , which is larger than sm and smaller than s M ), with 2 = h , and with 1 and 3 being the lines with slopes π2 −α and π 2 +α, respectively, through y1 , oriented towards increasing y-coordinates. Note that the slopes s1 , s2 , and s3 of 1 , 2 , and 3 , respectively, satisfy 0 < π s1 ≤ s2 ≤ s3 < π —in particular s2 ≤ π2 +β+α  ≤ π2 + 3α 8 < 2 +α = s3 ; π α α further, s3 = 2 + α < sm = π − 2 < s M = π + 2 < s1 + π = 3π 2 − α, given that α < π4 .

Now consider the line h parallel to h , passing through the midpoint of the edge z h z h+1 , and oriented towards increasing y-coordinates; h has h to its left, given that the midpoint of z h z h+1 is in Dρ , hence to the right of h in δ . Thus, h has  H,δ (and in particular y) to its left. Since the half-plane to the left of h represents the locus of the points of the plane that are closer to z h+1 than to z h , it follows that d(δ , z h y) > d(δ , z h+1 y). We now show that d(δ , z h y) > d(δ , z h+1 y) if h = s − 1. Recall that z h+1 = z s = u 0 = y and refer to Fig. 25. We exploit again the fact that the line h through y1 orthogonal to the line through z h and z h+1 has the drawing of H (and in particular y) to its left in δ ; since the slope of the edge z s−1 z s is in the interval (π + β − α  ; π + β + α  ) in δ , the same proof as for the case in which h ∈ {1, 2, . . . , s − 2} gives that h has the drawing of H to its left in δ . Consider the line h parallel to h , oriented towards increasing y-coordinates, and passing through the midpoint m h of the edge z h z h+1 . Differently from the case in which h ∈ {1, 2, . . . , s − 2}, the midpoint m h of z h z h+1 is not guaranteed to be in Dρ (in fact it is not in Dρ , although we do not prove this statement formally as we do not need it in the remainder), given that z h+1 = y is in H and hence not in Dρ . Since the half-plane to the left of h represents the locus of the points of the plane that are closer to z h+1 than to z h , we only need to show that the intersection point ph of the lines h and u lies to the right of y1 on u ; in fact, this implies that h has h (and hence y) to its left. Since z h lies inside Dρ , we have that x(z h ) ≥ x( pρ,u ). Further, x( pρ,u ) = x(y1 )+d y1 v −ρ. Moreover, by property 3 of  H,δ , we have that x(y1 ) = x(y )+ x(y )+x(z h ) d H (δ , y y1 ). Thus, we have that x(m h ) = ≥ 2 x(y )+x(y )+d H (δ ,y y1 )+d y1 v −ρ 2

d ( ,y y )+d

−ρ

= x(y ) + H δ  21 y1 v . For the sake of simplicity of the description, translate the Cartesian axes so that x(y ) = 0. d ( ,y y )+d −ρ Thus, x(m h ) ≥ H δ  21 y1 v . By Lemma 3.3, y is an internal vertex of βuv (G), hence y lies below u . Since ρ ≤ Y2 and z h lies in Dρ , the y-coordinate of y is smaller than the one

123

Discrete Comput Geom Fig. 25 Illustration for the proof that d(δ , z h y) > d(δ , z h+1 y) if h = s − 1

h

u

dH (Γδ, y y 1) y 1 H

dV (Γδ , y y 1) y

h

ph q h

pρ,u β

v zh

Dρ

ρ

mh z h+1 = y

of z h . It follows that the slope of z h z h+1 is greater than π . Further, z h and hence m h lie on or below the line h β with slope β through y . This implies that the slope of z hz h+1 is at most π + β. Thus, the slope sh of h is in the interval π2 ; π2 + β . We now derive a lower bound for the x-coordinate of ph . Let qh be the point such that x(qh ) = x(m h ) and y(qh ) = y( ph ). Consider the triangle m h ph qh . Since the y-coordinate of y is smaller than the one of z h , it is also smaller than the one of m h . Thus, d(δ , m h qh ) ≤ dV (δ , y y1 ). Since  sh ∈ π2 ; π2 + β , the angle  ph m h qh is at most β. Hence, d(δ , ph qh ) ≤ dV (δ , y y1 ) · tan(β). It follows that x( ph ) = x(m h ) − d(δ , ph qh ) ≥ d H (δ ,y y1 )+d y1 v −ρ − dV (δ , y y1 ) · tan(β). It remains to prove that this quan2 tity is larger than d H (δ , y y1 ), which is the x-coordinate of y1 . π , we have that tan(β) ≤ 1. It follows that Since β < α4 < 16

d H (δ ,y y1 )+d y1 v −ρ d ( ,y y )+d −ρ −dV (δ , y y1 )·tan(β) ≥ H δ  21 y1 v −dV (δ , y y1 ). 2 d ( ,y y )+d −ρ Hence, we want to establish that H δ  21 y1 v − dV (δ , y y1 ) > d H (δ , y y1 ), that is, d y1 v > 2dV (δ , y y1 ) + d H (δ , y y1 ) + ρ. Since d H (δ ,y y1 ) ρ ≤ y31 v , we need to prove that d y1 v > 6dV (δ ,y y1 )+3d . 2 We now express d y1 v as a function of β. This is done by looking at the

triangle whose vertices are y , v, and the point on u with the same xcoordinate as y . Since the angle of this triangle at v is β, we get that δ ,y y1 ) d y1 v = dV ( − d H (δ , y y1 ). Substituting this into the previous inequaltan(β)

dV (δ ,y y1 ) H (δ ,y y1 ) − d H (δ , y y1 ) > 6dV (δ ,y y1 )+3d , tan(β) 2 2dV (δ ,y y1 ) hence tan(β) < 6dV (δ ,y y1 )+5d H (δ ,y y1 ) . This inequality holds true since β <   H ,y y1 ) – note that dV ( H , y y1 ) = dV (δ , y y1 ) arctan 3dV ( H ,ydV y( 1 )+3d H ( H ,y y1 ) and d H ( H , y y1 ) = d H (δ , y y1 ), given that the drawing of H in δ coin-

ity, we need to have

cides with  H , except for the position of the vertex u, and given that y1 , y = u. This concludes the proof that d(δ , z h y) > d(δ , z h+1 y) if h = s − 1. • The third sub-path of Px y is a path Py y that connects y to y, that belongs to H , and that is distance-decreasing in  H,δ . This path exists since  H,δ satisfies property 6. Since the drawing of H in δ coincides with  H,δ , the path Py y is also distance-decreasing in δ . This concludes the proof of the lemma.



Given a strong circuit graph (G, u, v) such that G is not a single edge, we are in Case A or Case B depending on whether the edge uv exists or not, respectively. Thus, Lemmas 3.5–3.7 prove Theorem 3.4.

123

Discrete Comput Geom

It remains to show how to use Theorem 3.4 in order to prove Theorem 1.3. This is easily done as follows. Consider any 3-connected planar graph G and associate any plane embedding to it; let u and v be two consecutive vertices in the clockwise order of the vertices along the outer face of G. We have that (G, u, v) is a strong circuit graph. Indeed: (a) by assumption G is 2-connected—in fact 3-connected—and associated with a plane embedding; (b) by construction u and v are two distinct external vertices of G; (c) the edge uv exists and coincides with τuv (G), given that v immediately follows u in the clockwise order of the vertices along the outer face of G; and (d) G does not have any 2-cut, given that it is 3-connected. Thus, Theorem 3.4 can be applied in order to construct a planar greedy drawing of G. This concludes the proof of Theorem 1.3.

4 Conclusions In this paper we have shown how to construct planar greedy drawings of 3-connected planar graphs. It is tempting to try to use the graph decomposition we employed in this paper for proving that 3-connected planar graphs admit convex greedy drawings. However, despite some efforts in this direction, we have not been able to modify the statement of Theorem 3.4 in order to guarantee the desired convexities of the angles in the drawings. Thus, proving or disproving the convex greedy embedding conjecture remains an elusive goal. An interesting question related to the results of this paper is whether every 3connected planar graph admits a planar increasing-chord drawing; in fact 3-connected planar graphs are not known to admit increasing-chord drawings even when edge crossings are allowed (see, e.g. [11,26]). It might be possible to tackle this question by using the strong circuit graph decomposition we employed in this paper; however, new geometric constructions seem to be needed for the scope. Indeed, while the distancedecreasing paths we get in Case A of our inductive construction are actually increasingchord, those we get from Case B are not.

References 1. Alamdari, S., Chan, T.M., Grant, E., Lubiw, A., Pathak, V.: Self-approaching graphs. In: Didimo, W., Patrignani, M. (eds.) 20th International Symposium on Graph Drawing (GD’12). Lecture Notes in Computer Science, vol. 7704, pp. 260–271. Springer, Heidelberg (2013) 2. Angelini, P., Colasante, E., Di Battista, G., Frati, F., Patrignani, M.: Monotone drawings of graphs. J. Graph Algorithms Appl. 16(1), 5–35 (2012) 3. Angelini, P., Di Battista, G., Frati, F.: Succinct greedy drawings do not always exist. Networks 59(3), 267–274 (2012) 4. Angelini, P., Frati, F., Grilli, L.: An algorithm to construct greedy drawings of triangulations. In: Tollis, I.G., Patrignani, M. (eds.) 16th International Symposium on Graph Drawing (GD’08). Lecture Notes in Computer Science, vol. 5417, pp. 26–37. Springer, Berlin (2009) 5. Angelini, P., Frati, F., Grilli, L.: An algorithm to construct greedy drawings of triangulations. J. Graph Algorithms Appl. 14(1), 19–51 (2010)

123

Discrete Comput Geom 6. Barnette, D.: Trees in polyhedral graphs. Can. J. Math. 18, 731–736 (1966) 7. Bonichon, N., Bose, P., Carmi, P., Kostitsyna, I., Lubiw, A., Verdonschot, S.: Gabriel triangulations and angle-monotone graphs: Local routing and recognition. In: Hu, Y., Nöllenburg, M. (eds.) 24th International Symposium on Graph Drawing and Network Visualization (GD’16). Lecture Notes in Computer Science, vol. 9801, pp. 519–531. Springer, Cham (2016) 8. Bose, P., Morin, P., Stojmenovi´c, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. Wirel. Netw. 7(6), 609–616 (2001) 9. Chen, G., Yu, X.: Long cycles in 3-connected graphs. J. Comb. Theory Ser. B 86(1), 80–99 (2002) 10. Da Lozzo, G., Dujmovi´c, V., Frati, F., Mchedlidze, T., Roselli, V.: Drawing planar graphs with many collinear vertices. In: Hu, Y., Nöllenburg, M. (eds.) 24th International Symposium on Graph Drawing and Network Visualization (GD’16). Lecture Notes in Computer Science, vol. 9801, pp. 152–165. Springer, Cham (2016) 11. Dehkordi, H.R., Frati, F., Gudmundsson, J.: Increasing-chord graphs on point sets. J. Graph Algorithms Appl. 19(2), 761–778 (2015) 12. Dhandapani, R.: Greedy drawings of triangulations. Discrete Comput. Geom. 43(2), 375–392 (2010) 13. Eppstein, D., Goodrich, M.T.: Succinct greedy geometric routing using hyperbolic geometry. IEEE Trans. Comput. 60(11), 1571–1580 (2011) 14. Felsner, S., Igamberdiev, A., Kindermann, P., Klemz, B., Mchedlidze, T., Scheucher, M.: Strongly monotone drawings of planar graphs. In: 32nd International Symposium on Computational Geometry (SoCG’16). Leibniz International Proceedings in Informatics, vol. 51, pp. 37:1–37:15. Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern (2016) 15. Finn, G.G.: Routing and addressing problems in large metropolitan-scale internetworks. Tech. Rep. ISI/RR-87-180. University of Southern California, Information Sciences Institute (1987) 16. Frey, H., Rührup, S., Stojmenovi´c, I.: Routing in wireless sensor networks. In: Misra, S.C., Woungang, I., Misra, S. (eds.) Guide to Wireless Sensor Networks: Computer Communications and Networks, Chap. 4, pp. 81–111. Springer, Berlin (2009) 17. Goodrich, M.T., Strash, D.: Succinct greedy geometric routing in the Euclidean plane. In: Dong, Y., Du, D.Z., Ibarra, O.H. (eds.) 20th International Symposium on Algorithms and Computation (ISAAC’09). Lecture Notes in Computer Science, vol. 5878, pp. 781–791. Springer, Berlin (2009) 18. He, X., Zhang, H.: On succinct greedy drawings of plane triangulations and 3-connected plane graphs. Algorithmica 68(2), 531–544 (2014) 19. Hong, S.-H., Nagamochi, H.: Convex drawings of hierarchical planar graphs and clustered planar graphs. J. Discrete Algorithms 8(3), 282–295 (2010) 20. Kindermann, P., Schulz, A., Spoerhase, J., Wolff, A.: On monotone drawings of trees. In: Duncan, C.A., Symvonis, A. (eds.) 22nd International Symposium on Graph Drawing (GD’14). Lecture Notes in Computer Science, vol. 8871, pp. 488–500. Springer, Heidelberg (2014) 21. Kranakis, E., Singh, H., Urrutia, J.: Compass routing on geometric networks. In: Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG’99), pp. 51–54 (1999) 22. Kuhn, F., Wattenhofer, R., Zollinger, A.: An algorithmic approach to geographic routing in ad hoc and sensor networks. IEEE/ACM Trans. Netw. 16(1), 51–62 (2008) 23. Leighton, T., Moitra, A.: Some results on greedy embeddings in metric spaces. Discrete Comput. Geom. 44(3), 686–705 (2010) 24. Moitra, A., Leighton, T.: Some results on greedy embeddings in metric spaces. In: Ravi, R. (ed.) Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS’08), pp. 337–346. IEEE Computer Society (2008) 25. Nöllenburg, M., Prutkin, R.: Euclidean greedy drawings of trees. Discrete Comput. Geom. 58(3), 543–579 (2017) 26. Nöllenburg, M., Prutkin, R., Rutter, I.: On self-approaching and increasing-chord drawings of 3connected planar graphs. J. Comput. Geom. 7(1), 47–69 (2016) 27. Papadimitriou, C.H., Ratajczak, D.: On a conjecture related to geometric routing. In: Nikoletseas, S.E., Rolim, J.D.P. (eds.) First International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS’04). Lecture Notes in Computer Science, vol. 3121, pp. 9–17. Springer, Berlin (2004) 28. Papadimitriou, C.H., Ratajczak, D.: On a conjecture related to geometric routing. Theor. Comput. Sci. 344(1), 3–14 (2005) 29. Rao, A., Ratnasamy, S., Papadimitriou, C., Shenker, S., Stoica, I.: Geographic routing without location information. In: Johnson, D.B., Joseph, A.D., Vaidya, N.H. (eds.) Proceedings of the 9th Annual

123

Discrete Comput Geom International Conference on Mobile Computing and Networking (MobiCom’03), pp. 96–108. ACM, New York (2003) 30. Siva Ram Murthy, C., Manoj, B.: Ad Hoc Wireless Networks: Architectures and Protocols. Prentice Hall, Upper Saddle River (2004) 31. Toh, C.K.: Ad Hoc Mobile Wireless Networks: Protocols and Systems. Prentice Hall, Upper Saddle River (2002) 32. Wang, J.J., He, X.: Succinct strictly convex greedy drawing of 3-connected plane graphs. Theor. Comput. Sci. 532, 80–90 (2014)

123