{'fraction_non_alphanumeric': 0.037225687401826975, 'fraction_numerical': 0.010949628658136734, 'mean_word_length': 3.877203421346225, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Convexity-Increasing Morphs of Planar Graphs

We study the problem of convexifying drawings of planar graphs. Given any planar straight-line drawing of an internally 3-connected graph, we show how to morph the drawing to one with strictly convex faces while maintaining planarity at all times. Our morph is convexity-increasing, meaning that angles of inner faces never change from convex to reflex. We give an efficient algorithm that constructs such a morph as a composition of a linear number of steps where each step either moves vertices along horizontal lines or moves vertices along vertical lines. Moreover, we show that a linear number of steps is worst-case optimal. To obtain our result, we use a well-known technique by Hong and Nagamochi for finding redrawings with convex faces while preserving y-coordinates. Using a variant of Tutte's graph drawing algorithm, we obtain a new proof of Hong and Nagamochi's result which comes with a better running time. This is of independent interest, as Hong and Nagamochi's technique serves as a building block in existing morphing algorithms.


Introduction
A morph between two planar straight-line drawings Γ 0 and Γ 1 of a plane graph G is a continuous movement of the vertices from their positions in Γ 0 to their positions in Γ 1 , with the edges following along as straight-line segments between their endpoints. A morph is planar if it preserves planarity of the drawing at all times.
Motivated by applications in animation and in reconstruction of 3D shapes from 2D slices, the study of morphing has focused on finding a morph between two given planar drawings. The existence of planar morphs was established long ago [6,33], followed by algorithms that produce good visual results [17,19], and algorithms that find "piece-wise linear" morphs with a linear number of steps [2].
Our focus is somewhat different, and more aligned with graph drawing goals-our input is a planar graph drawing and our aim is to morph it to a better drawing, in particular to a convex drawing. A morph convexifies a given straight-line graph drawing if the end result is a (strictly) convex graph drawing, i.e. a planar straight-line graph drawing in which every face is a (strictly) convex polygon. For a survey on convex graph drawing, see [31].
We first observe that it is easy, using known results, to find a planar morph that convexifies a given graph drawing-we can just create a convex drawing with the same faces (assuming such a drawing exists), and morph to that specific drawing using the known planar morphing algorithms. In this paper, we impose a stronger condition: we want to find a convexifying morph which is also convexity-increasing, meaning that angles of inner faces never switch from convex to reflex. Besides the theoretical goal of studying continuous motion that is monotonic in some measure (e.g. edge lengths [22]), another motivation comes from visualization-a morph of a graph drawing should maintain the user's "mental map" [29] which means changing as little as possible, and making observable progress towards a goal. Most previous morphing algorithms fail to provide convexity-increasing morphs even if the target is a convex drawing because they start by triangulating the drawing. This means that an original convex angle may be subdivided by new triangulation edges, so there is no constraint that keeps it convex.
Related work. To the best of our knowledge there is no previous work on convexity-increasing morphs except for the case when the input graph is a path or a cycle. Connelly et al. [11] and Canterella et al. [7] gave algorithms to convexify a simple polygon while preserving edge lengths. Since their motions are "expansive", they are convexity-increasing. Aichholzer et al. [1] gave an algorithm to find a "visibility-increasing" morph of a simple polygon to a convex polygon; this condition implies the condition of being convexity-increasing.
In related work, there is an algorithm to morph a convex drawing to another convex drawing of the same graph while preserving planarity and convexity [3]. Such morphs are convexityincreasing by default, but do not address our problem since our initial drawing is not convex.
Many previous morphing algorithms find "piece-wise linear" morphs, where the morph is composed of discrete steps and each step moves vertices along straight lines. A morph is called linear if each vertex moves along a straight line at constant speed; different vertices are allowed to move at different speeds, and some may remain stationary. A linear morph is completely specified by the initial and final drawings. If, in addition, all the lines along which vertices move are parallel, then the morph is called unidirectional [2].
Alamdari et al. [2] gave an algorithm with runtime O(n 3 ) that takes as input two n-vertex planar straight-line drawings that are combinatorially the same, and constructs a planar morph between them that consists of a sequence of O(n) unidirectional morphs.
Our contribution. In this paper, we give the first algorithm that convexifies a given straightline planar drawing Γ via a planar convexity-increasing morph. The only requirement for Γ is that the plane graph G represented by Γ admits a strictly convex drawing. This is the case if and only if G is internally 3-connected; see Section 2.1 for the definition and related discussions.
In fact, we achieve the following stronger property-our morphs are composed of a linear number of horizontal and vertical morphs. A horizontal morph moves all vertices at constant speeds along horizontal lines; a vertical morph is defined analogously. These are special cases of unidirectional morphs. See Fig. 1 for an illustration. Orthogonality is a very desirable and well-studied criterion for graph drawing [14], in part because there is evidence that the human visual cortex comprehends orthogonal lines more easily [4,30,27]. Similarly, it seems natural that orthogonal motion should be easier to comprehend, though morphing algorithms have so far not explored this criterion.
Our main result is summarized in the following theorem.
Theorem 1. Let Γ be a planar straight-line drawing of an internally 3-connected graph G on n vertices. Then Γ can be morphed to a strictly convex drawing via a sequence of convexityincreasing planar morphs each of which is either a horizontal morph or a vertical morph. If Γ has a strictly convex outer face then the number of morphs in the sequence is at most r + 1, where r is the number of internal reflex angles in Γ. Without this restriction on Γ, but assuming that G is 3-connected, the number of morphs in the sequence is at most 1.5n. In general, the number of morphs is at most 3.5n.
Furthermore, there is an O(n 1+ω/2 ) time algorithm to find the sequence of morphs, where ω is the matrix multiplication exponent.
The run time is O(n 2.5 ) with Gaussian elimination, improved to O(n 2.1865 ) using the current fastest matrix multiplication method with ω ≈ 2.3728639 [23]. Our model of computation is the real-RAM-we do not have a polynomial bound on the bit-complexity of the coordinates of the vertices in the sequence of drawings that specify the morph. However, previous morphing algorithms had no such bounds either.
In terms of visualization, our algorithm has an advantage over the general morphing algorithm of Alamdari et al. [2]. That algorithm "almost contracts" vertices, which destroys the user's mental model of the graph. We do not use contractions, and therefore expect our morphs to be useful for visualizations.
Our proof of Theorem 1 uses some known techniques in graph drawing and graph morphing. As with some previous morphing results [2,3] a main ingredient of our proof is a result of Hong and Nagamochi [21] that gives conditions (and an algorithm) for redrawing a planar straight-line graph drawing to have convex faces, while preserving the y-coordinates of the vertices ("level planar drawings of hierarchical-st plane graphs," in their terminology). Angelini et al. [3] strengthened Hong and Nagamochi's result to strictly convex faces. We give a new proof of the strengthened result using Tutte's graph drawing algorithm. This speeds up Hong and Nagamochi's algorithm from O(n 2 ) to O(n ω/2 ). Our improvement in run-time also speeds up the run-time of the morphing algorithm of Alamdari et al. [2] from O(n 3 ) to O(n 1+ω/2 ). Theorem 1 guarantees the existence of a convexity-increasing morph to a convex drawing where the morph is composed of O(n) horizontal/vertical morphs. This is optimal in the worst case. In fact we show something stronger: There exists a drawing of an internally 3-connected graph with n vertices for which any convexifying planar morph composed of a sequence of linear morphing steps requires Ω(n) steps.
Organization. Our paper is structured as follows: We begin with preliminaries in Section 2. The proof of Theorem 1 is presented in Section 3, and the result about redrawing with convex faces is given in Section 4. The lower bound on the number of morphs (Theorem 2) is shown in Section 5. Finally, a discussion of the size of the grid needed for the intermediate drawings of our morph can be found in Section 6. We conclude with open problems in Section 7.

Preliminaries
In this section we formally define convex drawings, internally 3-connected graphs (Section 2.1) and y-monotone drawings (Section 2.2). We proceed by stating several useful properties of unidirectional morphs in Section 2.3. Finally, we address the concept of finding convex redrawings in Section 2.4.

Convex Drawings & Internal 3-Connectivity
Given a planar straight-line drawing Γ of a graph, its angles are formed by pairs of consecutive edges around a face, with the angle measured inside the face. An internal angle is an angle of an inner face. A reflex angle is one that exceeds π. A convex angle is at most π, and a strictly convex angle is less than π. A drawing Γ is convex if all its faces are drawn as convex polygons, i.e., angles of the inner faces are convex and angles of the outer face are reflex or flat (of angle 180 • ). The drawing is strictly convex if all faces are strictly convex.
Conditions for the existence of convex drawings. Throughout, we assume that our input graph has a convex drawing with the same faces and the same outer face as the input drawing. Necessary and sufficient conditions for the existence of such a convex drawing were given by Tutte [35], Thomassen [34], and Hong and Nagamochi [21]. These conditions can be tested in linear time by the algorithm of Chiba et al. [8].
Such conditions are usually stated for a fixed convex drawing of the outer face, but the conditions become simpler when, as in our case, the drawing of the outer face may be freely chosen-in particular, may be chosen to have no 3 consecutive collinear vertices. Internal vertices of degree 2 can also be dealt with directly: In a convex drawing, an internal vertex of degree 2 must be drawn as a point in the interior of the straight line segment formed by its two incident edges. This has two implications. The first is that a graph with an internal vertex of degree 2 has no strictly convex drawing. Secondly, for a convex drawing we might as well eliminate every internal degree 2 vertex, repeatedly replacing a path of two edge by a single edge. However, if this produces multiple edges, then there is no convex drawing.
With these observations, the necessary and sufficient conditions for the existence of a (strictly) convex drawing become quite simple to state. A plane graph G is internally 3-connected if the graph is 2-connected and any separation pair {u, v} is external, meaning that u and v lie on the outer face and that every connected component of (G − u − v) contains a vertex of the outer face of G. Observe that the two neighbours of an internal vertex of degree 2 form a separation pair that is not external. The results of Tutte [35], Thomassen [34], and Hong and Nagamochi [21] become: Lemma 3. Let G be a plane graph with outer face C. Then 1. G has a strictly convex drawing with outer face C if and only if G is internally 3-connected.
2. G has a convex drawing with outer face C if and only if repeatedly eliminating internal vertices of degree 2 produces a graph that has no multiple edges and is internally 3-connected.
Note that a separation pair which is not external can have both of its vertices on the outer face, see Fig. 2(b,c). For this reason, we refer to a separation pair which is not external as non-external 1 . Structure of internally 3-connected graphs. The following statement gives a characterization of external separation pairs and describes the structure of internally 3-connected graphs.
For an illustration see Fig. 2(a). 2. The outer face of H decomposes into two internally disjoint paths (u, w 1 , . . . , w j , v) and (v, w 1 , . . . , w , u) each with at least 3 vertices, i.e. j ≥ 1and l ≥ 1. 3. Vertices w 1 , . . . , w j belong to a connected component C of (H − u − v). 4. Vertices w 1 , . . . , w j belong to a connected component C of (H − u − v). 5. The plane graph (H − u − v) has no connected component other than C, C . 6. The components C and C are distinct.
Proof. If the six conditions hold, then clearly {u, v} is an external separation pair. On other hand, if {u, v} is an external separation pair, u and v belong to the outer face of H (1.). Further, the removal of u and v splits the graph into at least two connected components each of which has a vertex that belongs to the outer face of H. As a consequence, the outer face decomposes into two internally disjoint paths (u, w 1 , . . . , w j , v) and (v, w 1 , . . . , w , u) each with at least 3 vertices. Since (w 1 , . . . , w j ) is a path in (H − u − v), its vertices belong to a connected component C (3.). Similarly, (w 1 , . . . , w j ) is a path in (H − u − v), its vertices belong to a connected component C (4.). Since these two paths together with u and v cover the entire outer face of H, there can not be any more components (5.). Finally, since there are at least two components, C and C have to be distinct (6.).

y-Monotone Drawings
A face of a planar graph drawing is y-monotone if the boundary of the face consists of two y-monotone paths. A path is y-monotone if the y-coordinates along the curve realizing the path are strictly increasing. These definitions apply to general planar graph drawings, not just straight-line drawings. We note that the directed graphs that have drawings with y-monotone faces are the st-planar graphs, which are well-studied [13].

Linear and Unidirectional Morphs
A linear morph is completely specified by the initial and final drawings. We use the notation Γ 1 , Γ 2 to denote the linear morph from a drawing Γ 1 to a drawing Γ 2 . Restricting to linear morphs is a sensible way to discretize morphs-essentially, it asks for the vertex trajectories to be piece-wise linear. At first glance, the restriction to unidirectional morphs seems arbitrary and restrictive. However, as discovered by Alamdari et al. [2], it is easier to prove the existence of unidirectional morphs. Also, unidirectional morphs have many nice properties, as we explain in this section. Suppose we do a horizontal morph. Then every vertex must keep its y-coordinate. Alamdari et al. gave conditions on the initial and final drawing that guarantee that the horizontal morph between them is planar: Lemma 13] If Γ and Γ are two planar straight-line drawings of the same graph such that every line parallel to the x-axis crosses the same ordered sequence of edges and vertices in both drawings, then the linear morph from Γ to Γ is planar.
Observe that the conditions of the lemma imply that every vertex is at the same y-coordinate in Γ and Γ so the linear morph between them is horizontal. Also note that the lemma generalizes in the obvious way to any direction, not just the direction of the x-axis. We note several useful consequences of Lemma 5. Lemma 6. Let Γ 1 , Γ 2 , Γ 3 be three planar straight-line drawings where the linear morphs Γ 1 , Γ 2 and Γ 2 , Γ 3 are horizontal and planar. Then the linear morph Γ 1 , Γ 3 is a horizontal planar morph.
Proof. The morphs Γ 1 , Γ 2 and Γ 2 , Γ 3 are horizontal and planar, so every line parallel to the x-axis crosses the same ordered sequence of edges and vertices in Γ 1 and Γ 3 . Then by Lemma 5 the morph Γ 1 , Γ 3 is horizontal and planar.
Lemma 7. During a horizontal morph, the convexity status of each angle changes at most once, i.e. an angle cannot change more than once between reflex and convex or vice versa. If Γ 1 , Γ 2 is a horizontal morph and every convex internal angle of Γ 1 is also convex in Γ 2 then the morph is convexity-increasing.
Proof. This result is a generalization of [3,Lemma 7], and both are proved using basic properties of unidirectional morphs from [2]. Consider an angle formed by points a, b, c. If a and c both lie above b, or both lie below b, then the angle maintains its convexity status (convex or reflex) during any horizontal morph. So suppose that the ordering of the points by y-coordinate is a, b, c. Suppose that the clockwise angle abc is convex at two time points t and t with t < t during the horizontal morph. If we add the edge ac we obtain a triangle and the horizontal line through b crosses ac and b in the same order at both time points. Thus, the morph between t and t is planar by Lemma 5, so the angle is convex at all times between t and t .
We prove the contrapositive of the second statement. Suppose the horizontal morph Γ 1 , Γ 2 is not convexity-increasing. Then some internal angle changes from convex to reflex during the course of the morph. By the above statement, the angle must be convex in Γ 1 and reflex in Γ 2 .
As usual, we say two planar drawings of a graph G have the same combinatorial embedding if they have the same clockwise cyclic ordering of edges around the outer face and around each inner face. Alamdari et al. gave a further condition that implies the hypothesis of Lemma 5.
Observation 8. [2, Lemma 13] Let Γ be a planar graph drawing of a graph G in which all faces (including the outer face) are y-monotone and let Γ another planar drawing of G that has the same combinatorial embedding, the same y-coordinates of vertices, and y-monotone edges. Then every line parallel to the x-axis crosses the same ordered sequence of edges and vertices in both drawings.
Note that the observation fails for non-y-monotone faces-imagine a rectangle with one stalactite from the top and one stalagmite from the bottom such that a horizontal line through the middle of the rectangle intersects the stalactite and then the stalagmite. This order can be switched without changing the combinatorial embedding or the y-coordinates of the vertices. Observation 8 and Lemma 5 are combined in [2], but we need the more general formulation of Observation 8 for planar drawings that are not necessarily straight-line.
The final ingredient we need in order to make use of the above lemmas is a way to redraw a graph to preserve the combinatorial embedding and the y-coordinates of the vertices, while improving convexity. We will again follow Alamdari et al. [2] and make use of a result of Hong and Nagamochi which is described in the next section.

Redrawing with Convex Faces while Preserving y-Coordinates
We build upon an O(n 2 ) time algorithm due to Hong and Nagamochi [21] that redraws a planar graph to have convex faces while preserving the y-coordinates of the vertices. Angelini et al. [3] strengthened the result to strictly convex faces by perturbing vertices to avoid angles of 180 • . They did not analyze the run-time. Both [21] and [3] expressed their results in terms of level planar drawings of hierarchical-st plane graphs. Their original statements and further explanations can be found in Appendix A.
In Section 4, we give a new proof of Hong and Nagamochi's result using Tutte's graph drawing algorithm. This is quite different from the previous approaches and results in an improved running time of O(n 1.5 ) without fast matrix multiplication, O(n 1.1865 ) with: Lemma 9 (based on [21,3]). Let Γ be a planar drawing of an internally 3-connected graph G such that every face is y-monotone (including the outer face). Let C be a strictly convex straight-line drawing of the outer face of G such that every vertex of C has the same y-coordinate as in Γ. Then there is a strictly convex straight-line drawing Γ of G that has C as the outer face and such that every vertex of Γ has the same y-coordinate as in Γ. Furthermore, Γ can be found in time O(n ω/2 ), where ω is the matrix multiplication exponent.

Computing Convexity-Increasing Morphs
In this section we prove Theorem 1. In fact, we show multiple variants of Theorem 1, starting with a highly specialized version and proceeding to more and more general ones, which use the more specialized cases as building blocks.

A Simple Case: Morphing y-Monotone Drawings
To give some intuition about our general proof strategy, we first consider an easy case where the outer face C of Γ is strictly convex and all faces are y-monotone. Then we can immediately apply Lemma 9 with the outer face fixed to obtain a new straight-line strictly convex drawing Γ with all vertices at the same y-coordinates. By Observation 8 every line parallel to the x-axis crosses the same ordered sequence of edges and vertices in Γ and in Γ . Then by Lemma 5 the morph from Γ to Γ is planar. Also it is a horizontal morph. Thus we have a morph from Γ to a strictly convex drawing Γ by way of a single horizontal morph. Furthermore, the morph is convexity-increasing by Lemma 7.

Morphing Drawings with a Convex Outer Face
We next consider the case where the outer face is convex (but not necessarily strictly convex), and where the inner faces are not necessarily y-monotone.
Assume Γ has no horizontal edges (we show how to ensure this later on). A face f is y-monotone if and only if it has only one local maximum and only one local minimum, where a vertex v is a local minimum (local maximum) of face f if the neighbors of v in f lie above v (below v, respectively). A local extremum refers to a local minimum or a local maximum.
Overview. As in Section 3.1, we begin by performing a horizontal morph. Observe that such a morph preserves the local extrema and does not change their convexity status. Thus the only reflex angles that can be made convex via a horizontal morph are the h-reflex angles, where an angle of inner face f is called h-reflex if it is reflex and occurs at a vertex that has one neighbor in f above and the other below-equivalently, the angle is reflex and is not a local extremum of f . We will show that a single horizontal morph suffices to convexify all the internal angles that are not local extrema. The plan is to then conceptually "turn the paper" by 90 • and perform a vertical morph to make any v-reflex angle convex, where an angle of inner face f is called a v-reflex angle if it is reflex and occurs at a vertex that has one neighbor in f to the left and the other to the right. By continuing to alternate between the horizontal and the vertical direction, we eventually end up with a convex drawing and, thus, prove Theorem 1 for the case of a convex outer face.
A horizontal morphing step. To find the desired horizontal morph we will apply Lemma 9, and to do that, we must first augment Γ to a drawing with y-monotone faces by inserting y-monotone edges which are not necessarily straight-line. For an example see Fig. 3. This is a standard operation in upward planar (or "monotone") drawing [13, Lemma 4.1] [28, Lemma 3.1], but we need the stronger property that the new edges are only incident to local extrema; otherwise we would relinquish control of convexity at that vertex. We will use: Lemma 10. Any straight-line planar drawing of an internally 3-connected graph can be augmented to have y-monotone inner faces by adding edges such that each edge can be drawn as a y-monotone curve joining two local extrema in some face. The augmented graph is internally 3-connected. Furthermore, the edges can be found in time O(n log n).
Proof. We first note that a face is y-monotone if and only if it has no reflex local extrema. Our proof is by induction on the number of reflex local extrema in all inner faces of the drawing. If there are none, then all inner faces are y-monotone. Otherwise, consider an inner face f that has a local extremum u. For an illustration consider Fig. 3. Assume without loss of generality that u is a local minimum. We want to find a local extremum v below u such that a y-monotone curve can be added from v to u within face f . To construct the curve go vertically downwards from u to the first point p u on the boundary of f , and then follow a y-monotone chain of f 's boundary downwards from p u to a local minimum v. Adding the edge (u, v) divides f into two faces, and decreases the total number of local extrema. We note that Pach and Tóth [28] used a similar idea to triangulate with monotone curves, although their curves stopped at the first vertex on f 's boundary and we must continue to the first local minimum. Since we will only insert inner edges, the graph remains internally 3-connected.
To complete the proof we briefly describe how the set of augmenting edges can be found in time O(n log n). We deal with the local reflex minima; the maxima can be dealt with in a second phase. Find a trapezoidization of the drawing [12] in O(n log n) time. This gives the point p u for each local reflex minimum u in face f . We can preprocess the graph in time O(n) to find, for each edge e in face f , the local minimum v that is reached by following a y-monotone chain downward from e in f . This gives the set of augmenting edges. We must still find the cyclic order of augmenting edges incident with each vertex v. We separate into those that arrive at v from the left and those that arrive from the right. Within each of these sets, we sort by the y-coordinate of points p u .
This observation allows us to prove the following: Lemma 11. Let Γ be a straight-line planar drawing of an internally 3-connected graph with a convex outer face and no horizontal edge. There exists a horizontal planar morph to a straight-line drawing Γ such that Γ has a strictly convex outer face and every internal angle that is not a local extremum is strictly convex in Γ . Furthermore, the morph is convexity-increasing, and can be found in time O(n ω/2 ), where ω is the matrix multiplication exponent.
Proof. Use Lemma 10 to augment Γ with a set of edges A such that Γ ∪ A is a planar drawing in which all faces are y-monotone, and any edge of A goes between two local extrema in some inner face. This takes O(n log n) time. Let C be the outer face of Γ. Create a new drawing of C, call it C , that is strictly convex, but preserves the y-coordinates of vertices.
By Lemma 9 with the outer face C we obtain (in time O(n ω/2 )) a new straight-line strictly convex drawing Γ ∪ A with all vertices at the same y-coordinates as in Γ. (Here A is a set of straight-line edges corresponding to A.) By Observation 8 every line parallel to the x-axis crosses the same ordered sequence of edges and vertices in Γ ∪ A and in Γ ∪ A . Then by Lemma 5 the morph from Γ to Γ is a planar horizontal morph.
Any internal angle of Γ that is not a local extremum has no edge of A incident to it, and thus becomes strictly convex in Γ . Any internal angle of Γ that is a local extremum maintains its convex/reflex status in Γ . Thus by Lemma 7 the morph is convexity-increasing. The run-time to find the morph (i.e., to find Γ ) is O(n ω/2 ).
Making progress. Lemma 11 generalizes to directions d other than the horizontal direction: for any direction d that is not parallel to an edge of Γ, there exists a convexity-increasing unidirectional (with respect to d) morph that convexifies all internal angles that are not extreme in the direction orthogonal to d. Thus, if we do not insist on a sequence of horizontal and vertical morphs, we immediately obtain a proof of Theorem 1 for the case of a convex outer face, since, for each reflex angle, we can choose a direction d that convexifies it.
In order to prove the stronger result that uses only two orthogonal directions, we need to alternate between the horizontal and the vertical direction. Note that after one application of Lemma 11, we do not necessarily obtain a drawing which contains a v-reflex vertex, see Fig. 4(a,b). In order to ensure that our algorithm makes progress after every step, we prove a strengthened version of Lemma 11, which ensures that there is at least one h-reflex or v-reflex vertex available after each step.
Lemma 12. Let Γ be a straight-line planar drawing with a convex outer face and no horizontal edge. There exists a horizontal planar morph to a straight-line drawing Γ such that (i) the outer face of Γ is strictly convex, (ii) every internal angle that is not a local extremum is convex in Γ , (iii) Γ has no vertical edge, and (iv) if Γ is not convex, then it has at least one v-reflex angle. Furthermore, the morph is convexity-increasing, and can be found in time O(n ω/2 ).
Proof. We first apply Lemma 11 to obtain a morph from Γ to a drawing Γ that satisfies (i) and (ii). If Γ satisfies all the requirements, we are done. Otherwise we will achieve the remaining properties by shearing the drawing Γ . Eliminating vertical edges via a horizontal shear is easy, so we concentrate on the requirement (iv) about v-reflex angles. Suppose Γ is not convex and has no v-reflex angle. Consider any reflex angle of Γ , say at vertex u in inner face f . Note that u must be a local extremum otherwise it would be convex in Γ . We will apply a horizontal shear transformation to create a drawing Γ in which the angle at u becomes v-reflex, i.e., in which the x-coordinate of u is between the x-coordinates of its two neighbors in f . Furthermore, the shear should eliminate all vertical edges, e.g., see Fig. 4. The shear can be found in linear time.
Since shearing is an affine transformation, Γ has the same convex/reflex angles as Γ . Thus Γ satisfies all the properties. The linear morph Γ , Γ is a planar horizontal morph that preserves the convex/reflex status of every angle. By Lemma 6 the morph Γ, Γ is a horizontal We are now ready to prove Theorem 1 for the case of a convex outer face.
Proof of Theorem 1 for the case of a convex outer face. If the given drawing Γ has no h-reflex angle, or has a horizontal edge, then we use one vertical shear as in the proof of Lemma 12 to remedy this. Then we apply Lemma 12 alternately in the horizontal and vertical directions until the drawing is convex. In each step there is at least one h-reflex or v-reflex angle that becomes convex. Thus, the number of morphing steps is at most r + 1 ≤ n, where r is the number of inner reflex angles in Γ. The resulting total run-time is O(n 1+ω/2 ).

Morphing Drawings of 3-Connected Graphs
In this section we prove the case of Theorem 1 where the outer face of Γ is not assumed to be convex. However, we will assume that the given graph G is 3-connected (instead of internally 3-connected). Overview. On a high level, our approach works as follows. We first augment the outer face of Γ with edges from its convex hull to obtain a drawing of an augmented graph with a convex outer face. We apply the results from Section 3.2 to morph to a strictly convex drawing and then remove the extra edges one-by-one. After each edge is removed we morph to a strictly convex drawing of the reduced graph using at most three horizontal or vertical morphs.
Augmenting the outer face. Compute the convex hull of Γ. Any segment of the convex hull that does not correspond to an edge of G becomes a new edge that we add to G. Let A denote the new edges and G ∪ A denote the augmented graph with straight-line planar drawing Γ ∪ Γ A . Note that adding edges maintains 3-connectivity. Each edge e ∈ A is part of the boundary of an inner face f e of Γ ∪ Γ A . We call f e the pocket of e. We apply the result of Section 3.2 to obtain a strictly convex drawing of G ∪ A, see Fig. 5(a). Note that the techniques used in that section give us a drawing with no horizontal or vertical edges. We remark that this step is the reason why we limit ourselves to 3-connected graphs in this subsection: Adding the convex hull edges in a drawing of an internally 3-connected graph may create non-external separations pairs, see Fig. 6(a). This would prevent us from using the algorithm from Section 3.2 as this algorithm uses Lemma 9 which requires the input graph to be internally 3-connected. Popping a pocket outward. In this final step, we describe a way to remove an edge of A and "pop" out the vertices of its pocket so that they become part of the convex hull. Lemma 9 serves once again as an important subroutine. We make ample use of the fact that we may freely specify the desired subdrawing of the outer face after each application of Lemma 9, as long as we maintain either the x-coordinates or the y-coordinates of all vertices.
We remark that the following lemma applies to internally 3-connected graphs, not only 3-connected graphs. We plan to use it in the following section, in which we prove Theorem 1 in its general form. In fact, the final algorithm will use the entire procedure described in this section as a subroutine (we will augment the internally 3-connected graph such that adding the convex hull edges does not create non-external separation pairs).
Lemma 13. Let Γ be a strictly convex drawing of an internally 3-connected graph G without vertical edges and let e be an edge on the outer face . Suppose that G − e is internally 3-connected. Then Γ − e can be morphed to a strictly convex drawing of G − e without vertical edges via at most three convexity-increasing morphs, each of which is horizontal or vertical. Furthermore, the morphs can be found in time O(n ω/2 ).
Proof. Our morph will be specified by a sequence of drawings, Γ, Γ 1 , Γ 2 , Γ 3 , where the first and last morphs are vertical and the second morph, which we can sometimes skip, is horizontal.
Let e = (u, v). We first perform a vertical morph from Γ to a strictly convex drawing Γ 1 in which vertex u is top-most or bottom-most and which does not contain vertical or horizontal edges. Since Γ is strictly convex and has no vertical edges, it is also x-montone. Therefore, the desired drawing Γ 1 can be found by choosing some strictly convex drawing of the outer face in which u is extreme while maintaining the x-coordinates of all vertices, and then using one application of Lemma 9 (for vertical morphs). Additional, we may need to apply a vertical shearing transformation in order to get rid of horizontal edges. This is easily done while still guaranteeing that u is extreme in the y-direction. Analogous to Section 3.1, by combining Observation 8, Lemma 5 and Lemma 7 we conclude that the horizontal morph Γ, Γ 1 is planar and convexity-increasing.
For the remainder of the proof, assume without loss of generality that u is the top-most vertex and that v lies to the right of u in Γ 1 . The other cases are symmetric. Let p uv denote the path from u to v in f e − e. We distinguish two cases depending on the shape of f e in Γ 1 . Case 1: The path p u,v is x-monotone in Γ 1 , see Fig. 5(b). In this case we can skip the second step of the morph sequence. We will remove e and compute a vertical morph from Γ 1 − e to a strictly convex drawing Γ 3 of G − e without vertical edges. Once again, this can be done by combining Lemma 9 (for vertical morphs), Observation 8, Lemma 5 and Lemma 7 as long as we can specify a strictly convex drawing of the outer face of Γ 1 − e in which the x-coordinates match those of Γ 1 . It suffices to compute a suitable new reflex chain for p uv , see Fig. 5(b). Case 2: The path p uv is not x-monotone. In this case we will compute a horizontal morph from Γ 1 to a strictly convex drawing Γ 2 in which u and v are the unique left-most and the unique right-most vertices and which does not contain a vertical edge. Once again, this can be done by combining Lemma 9, a horizontal shearing transformation, Observation 8, Lemma 5 and Lemma 7 as long as we can specify a strictly convex drawing of the outer face of Γ 1 in which u and v are the left-most and right-most vertices and the y-coordinates match those of Γ 1 . This is possible because u is top-most, see Fig. 5(c).
In the drawing Γ 2 the pocket f e is convex with extreme points u and v so the path p uv is x-monotone and, hence, by Case 1, there is a vertical morph from Γ 2 − e to a strictly convex drawing Γ 3 of G − e.
Observe that each application of Lemma 13 increases the number of vertices of G on the convex hull. Thus, the proof of Theorem 1 follows by induction on the number of convex hull vertices. We have used at most three horizontal and vertical morphs per pocket. This can be decreased to two morphs per pocket by noting that each application of Lemma 13 involves a vertical-horizontal-vertical morph sequence, and Lemma 6 allows us to compress two consecutive vertical morphs into one. Since there are at most n/2 pockets, the number of morphs needed to deal with pockets is at most n. The number of morphs to obtain the initial drawing of G ∪ A is at most r + 1 ≤ n, where r is the number of internal reflex angles in Γ ∪ Γ A . Thus, the total number of morphs is bounded by 2n. We can improve this bound to 1.5n: Each pocket is defined by two convex hull vertices, which cannot contribute to the r + 1 initial morphs. Therefore, we can charge one of the two morphs per pocket to one of its two convex hull vertices. The run time of the algorithm is O(n 1+ω/2 ).

Morphing Drawings of Internally 3-Connected Graphs
So far, if the given drawing does not have a convex outer face, we have restricted our attention to the class of 3-connected graphs. The only reason why the approach described in Section 3.3 is not able to handle the case of internally 3-connected graphs is that the addition of the convex hull edges A may create non-external cut pairs, see Fig. 6(a). As a result, the augmented drawing Γ G ∪ Γ A is no longer a valid input for Lemma 9. In this section we extend our algorithm such that it is able to convexify drawings of internally 3-connected graphs and, thus, we conclude the proof of Theorem 1 in its general form. (c) Geometrically, we embed P e very close to P e . This is possible regardless of the shape of the pocket.
Overview. Let Γ be a straight-line planar drawing of an internally 3-connected graph G = (V, E). As a first step, we augment the outer face of Γ by adding new edges and vertices near each pocket. The goal of this step is to ensure that we can add convex hull edges without introducing non-external cut pairs. We then apply the algorithm from Section 3.3, which results in a drawing in which all the new vertices appear on the strictly convex outer face. Finally, we remove the new vertices one-by-one; gradually turning the strictly convex drawing of the augmented graph into a strictly convex drawing of G.
In slightly more detail, our method involves the following steps: Step 1: Augmenting the outer face. We will augment the graph G to G , and then augment the drawing Γ to Γ , which involves geometric arguments. The goal is to ensure that G is internally 3-connected and has the additional property that adding convex hull edges to Γ does not introduce non-external cut pairs, as, for example, in Fig. 6(a). We will show that bad cases like this only arise when a pocket has a vertex that is part of a separating pair. Thus, our method will be to add an extra "bufffer" layer of vertices to each pocket boundary, while ensuring that each buffer vertex is not part of a separating pair.
Step 2: Convexifying the augmented drawing. The goal of this step is to find a convexityincreasing morph from the drawing Γ of the augmented graph G to a strictly convex drawing of G . In principal, the idea for accomplishing this task is very simple: we just apply the algorithm described in Section 3.3 to Γ . The challenging aspect is, that this algorithm uses Lemma 9 as a subroutine and, thus, we need to ensure that the precondition of Lemma 9, i.e., internal 3-connectivity of the input graph, is satisfied whenever Lemma 9 is used.
Step 3: Removing the additional vertices. At this point we have a strictly convex drawing of G . We must now "reverse" the augmentation process, removing vertices of G to get back to G. After each vertex is removed we will morph to obtain a strictly convex drawing. As in Step 2, the graph must remain internally 3-connected at each step. We will therefore treat the augmentation process of Step 1 as an iterative process, adding vertices one-by-one and ensuring that the graph is internally 3-connected at each step.
We now give further details on these three steps.
Step 1: Augmenting the outer face. We compute the convex hull of Γ. Let e be a convex hull edge with e / ∈ E. The following steps are illustrated in Fig. 6(b). Let P e = (v 0 , v 1 , . . . , v k+1 ) be the unique path on the outer face of Γ such that P e + e is a cycle with G − P e in its exterior. We introduce 2k + 1 new vertices that form a path P e connecting v 0 and v k+1 : Note that every inner vertex v i of P e gets a "private copy" v b i in P e . Two consecutive copies v b i and v b i+1 are connected via one other vertex which is equipped with two labels v c i = v a i+1 , which will simplify the notation later on. Additionally, we add the edges Geometrically, the new path P e is embedded in a planar fashion very close to P e , see Fig. 6(c). This can be accomplished regardless of the shape of P e : Assume that k ≥ 2 and let ε be the smallest distance between any pair of disjoint edges on the cycle P e + e. For i = 1, . . . , k, we place v b i on the angular bisector of the outer angle at v i such that its distance to v i is smaller than ε/2.
. We make sure that during this procedure no vertex is placed in the exterior of the convex hull of Γ; with the following exceptions: the vertices v a 1 and v c k play a special role and are placed close to v 0 and v k+1 , respectively, such that they do appear on the convex hull of the augmented drawing.
Note that for the special case of small pockets with k = 1, the value ε would not be welldefined, as there are no disjoint edges on P e + e. However, in this case it is easy to directly compute an embedding of P e with the desired properties (i.e. planarity; and only v a 1 and v c k appear on the convex hull). We repeat the process for all convex hull edges e / ∈ E of Γ and use G = (V , E ) and Γ to denote the resulting plane graph and drawing respectively. The total run-time for this step is dominated by the time to compute the values ε, which can be done in O(n 2 ) total time. We remark that this step could be implemented more efficiently, for example by computing a medial axis [9]. However, since our total runtime is ω(n 2 ), we refrain from stating the details.
We will now prove that G is internally 3-connected. Keeping in mind our plan for Step 3, we will add the vertices of G one-by-one, showing that each addition preserves the property of being internally 3-connected. We begin with some basic operations that preserve internal 3-connectivity. With these operations in hand, we can show that G is internally 3-connected, and-more strongly-that we can build G by adding one vertex at a time, preserving internal 3-connectivity.
is the set of all vertices whose upper index is b, and where V ac is the set of the remaining vertices (whose upper index is a and/or c).
Lemma 16. Starting with G and adding the vertices of V ac one-by-one in any order and then the vertices of V b one-by-one in any order produces an internally 3-connected graph at each step.
Proof. The addition of each vertex of V ac maintains internal 3-connectivity by Lemma 14. The addition of each vertex of V b maintains internal 3-connectivity by Lemma 15.
Step 2: Convexifying the augmented drawing. As mentioned above, the plan is to apply the algorithm described in Section 3.3 to Γ . That algorithm adds the convex hull edges of Γ and then iteratively removes these edges while performing some morphing steps before and after each removal. Each morphing step requires one application of Lemma 9. Therefore, in order to prove the correctness of Step 2, we need to ensure that before and after each removal of a convex hull edge, the input graph is internally 3-connected.
We begin by observing that the new vertices of G are not part of separation pairs. Then we show that adding a convex hull edge is safe when none of the vertices of its pocket are in separating pairs. Observation 17. No vertex of V \ V is in a separating pair of G .
Proof. By construction, removing any one of these vertices can not introduce a cut vertex.
We now give one more operation that preserves internal 3-connectivity.
Lemma 18. Let H be an internally 3-connected graph, with vertices a and b on the outer face. Let P be one of the paths from a to b on the outer face. Assume that no vertex of P is part of a separating pair in H. Let H be the result of adding the edge (a, b) to enclose P in an internal face. Then H is internally 3-connected.
Proof. Suppose that H has a separation pair {u, v}. Then this pair is also separating in H. Further, since H is internally 3-connected, {u, v} is an external separation pair of H. Since both u and v do not belong to P , Observation 4 implies that a and b belong to the same component of (H − u − v). Thus, adding the edge between a and b maintains the six conditions of Observation 4 (in particular, Condition 2 holds as a and b remain on the outer face). Therefore, {u, v} is an external separation pair of H .
Recall that the construction of Γ ensures that all convex hull edges e which do not correspond to edges of G have the form e = {v a 1 , v c k }, where v a 1 , v c k are the first and last internal vertex of one of the paths P e . By Observation 17 the interior vertices of P e form a path P on the outer face which does not contain any vertices that are part of a separation pair. Further, adding the edge e encloses P in an internal face. Thus, we obtain: Corollary 19. Let A denote the set of convex hull edges of Γ which do not correspond to edges of G . Then, for any S ⊆ A the plane graph G + S is internally 3-connected.
Step 3: Removing the additional vertices. At this point we have a strictly convex drawing of G and want to convert it to a strictly convex drawing of G. We will remove the vertices of V b iteratively; one-by-one. After each such removal, we will perform up to two morphing steps in order to recover a strictly convex drawing of the reduced graph. Recall that by Lemma 16, all the intermediary graphs are internally 3-connected and, thus, they are valid inputs for Lemma 9. Proof. Without loss of generality, we may assume that v c i is located to the bottom-right of v a i and that v b i is located to the right of the oriented line Fig. 7(a). We distinguish four cases regarding the position of the vertex v i , for an illustration see Fig. 7   i , such every vertex in C has the same y-coordinate as in Γ B − v b i (we can easily find such a drawing C by adding v i to the convex hull of Γ B − v b i in a strictly convex fashion). Then, Lemma 9 applied to Γ B − v b i and C (potentially followed by a horizontal shearing transformation in order to remove vertical edges), yields the desired drawing Γ . Analogous to Section 3.1, by combining Observation 8, Lemma 5 and Lemma 7 we conclude that the horizontal morph Γ B − v b i , Γ is planar and convexity-increasing.
; and we are not in Case 1 or Case 2. Let C be a strictly convex drawing of the outer face of G − B − v b i , such every vertex in C has the same x-coordinate as in Γ B − v b i (we can easily find such a drawing C by adding v i to the convex hull of Γ B − v b i in a strictly convex fashion). Then, Lemma 9 (for vertical morphs) (potentially followed by a vertical shearing transformation in order to remove horizontal edges) applied to Γ B − v b i and C yields the desired drawing Γ . Analogous to Section 3.1, by combining Observation 8, Lemma 5 and Lemma 7 we conclude that the vertical morph Γ B − v b i , Γ is planar and convexity-increasing. Case 4: we are not in Case 1, Case 2 or Case 3. We reduce to Case 2 or Case 3: using a shearing transformation along the x-axis (or along the y-axis), we obtain a drawing Γ B of G − B satisfying the preconditions of Case 3 (or Case 2). Analogous to Section 3.1, by combining Observation 8, Lemma 5 and Lemma 7 we conclude that the linear morph Γ B , Γ B is planar and convexity-increasing.
Starting with the drawing Γ of G and iterating Lemma 20, we obtain a strictly convex drawing of G − V b . By construction, we can simply remove all the vertices of V ac to obtain a strictly convex drawing of G.
Observation 21. Let Γ ac be a strictly convex drawing of G − V b . Then, Γ ac − V ac is a strictly convex drawing of G.
We summarize: Proof of Theorem 1. We analyze the three steps of the algorithm individually.
Step 1: We begin by augmenting G and Γ to G and Γ . As discussed in the corresponding section, this can be done in O(n 2 ) time.
Step 2: Next, we apply the algorithm from Section 3.3 to G and Γ . This algorithm was designed for 3-connected graphs. However, note that Lemma 13 applies to internally 3-connected graphs (not just 3-connected graphs). Therefore, the algorithm also works for internally 3-connected graphs as long as adding convex hull edges and then successively removing them never creates a plane graph which is not internally 3-connected. This is the case by Corollary 19. Thereby, we obtain in O(n 1+ω/2 ) ⊆ O(n 1+ω/2 ) time a convexity-increasing morph from Γ to a strictly convex drawing of G , where n is the number of vertices of the augmented graph G . This morph is also convexity-increasing with respect to the subdrawing of G as every internal angle of Γ is also internal in Γ . The upper bound on the number of vertical / horizontal morphing steps guaranteed by the algorithm is 1.5n .
A more careful analysis (together with a slight modification of the construction of Γ ) shows that we can actually guarantee at most 1.5n < 1.5n steps. Recall that the bound of 1.5n is obtained as follows: first, we have up to r < n morphing steps to convexify Γ + Γ A where Γ A is the set of convex hull edges of Γ and where r is the number of inner reflex angles of Γ + Γ A . Then, we have up to 2 morphs for each of the up to n /2 pockets. This bound of 2n was further decreased to 1.5n by charging one of the two morphs per pocket to one of the convex hull vertices of the pocket, as such a vertex can not have an internal reflex angle. We will show in the following paragraphs that the number r is upper bounded by n. Combined with the fact that number of pockets in Γ and Γ is identical (i.e., Γ has at most n/2 pockets), this gives a bound of 2n morphs. Once again this can be decreased by charging one of the two morphs per augmented pocket to one of the two convex hull vertices of the original pocket, which gives the desired bound of 1.5n.
The construction of Γ ensures that an outer angle at a vertex v b i ∈ V b is reflex if and only if the outer angle at the corresponding vertex v i is reflex in Γ. Other angles at v b i can not be reflex. Further, if the outer angle at v i is reflex in Γ then v i has no reflex angle in Γ . Consequently, we can charge the inner reflex angles of the vertices v b i to their counterparts v i . Let e be one of the convex hull edges of G . We observe that the first inner vertex v a 1 and the last inner vertex v c k of P e have outer angles which are reflex and, thus, they have no inner angle which is reflex. Each of the vertices v a i with 2 ≤ i ≤ k has one angle α i of degree π and multiple smaller angles. We modify the construction of Γ as follows: instead of placing v a i in the center of the segment v b i−1 v b i , we shift its position slightly towards P e . This turns α i into a convex angle. The remaining faces incident to v a i are triangles and, thus, v a i has no incident reflex angle. We remark the the shift of v a i needs to be small enough such that it does not create any new reflex angles at one of the vertices of V b . This is easy to achieve.
We have shown that each vertex of V \ V with upper index a / c has no inner reflex angle in Γ + Γ A . Further, we have shown that the remaining vertices of V \ V , i.e. the vertices with upper index b, may have inner reflex angles, but only if their respective counterparts have no inner reflex angle. Altogether, this yields we obtain r ≤ n.
Step 3: Finally, we iteratively apply Lemma 20. Each application increases the number of vertices of G on the convex hull. Thus, by induction we arrive at a strictly convex drawing of G. Each of the intermediary morph steps is convexity-increasing with respect to the respective augmented graph. Once again, since every internal angle of Γ remains internal in (all) the augmented graph(s), we have that the morphing sequence is convexity-increasing for G as well. The number of morphing steps is bounded by 2n and the time required to obtain the entire sequence sums up to O(n 1+ω/2 ) ⊆ O(n 1+ω/2 ).
Summing up, we end up with 3.5n morphing steps and a runtime of O(n 1+ω/2 ).

Using Tutte's Algorithm to Find Convex Drawings Preserving y-Coordinates
In this section we prove Lemma 9 using Tutte's graph drawing algorithm. We obtain an algorithm that produces a straight-line strictly convex drawing preserving y-coordinates and runs in O(n ω/2 ) time, where ω is the matrix multiplication exponent. The idea of using Tutte's algorithm to prove Lemma 9 is known to some in the graph drawing community, but it has not been published and is not widely known. In his paper, "How to Draw a Graph," [36] Tutte showed that any 3-connected planar graph G = (V, E) with a fixed convex drawing C of its outer face has a convex drawing with outer face C that can be obtained by solving a system of linear equations. Let V I be the internal vertices of G and for v ∈ V I let variables (x v , y v ) represent the coordinates of vertex v. For each vertex v ∈ C let (x v , y v ) be its (fixed) coordinates. Let d v be the degree of vertex v. Consider the system of equations: Tutte proved that this system of equations has a solution and that the solution gives a convex drawing of G with outer face C. The drawing is strictly convex so long as C is strictly convex. We wish to apply Tutte's result more generally to graphs that are internally 3-connected, rather than 3-connected. Although the graphs are more general, we are only concerned with strictly convex drawings of the outer face. This makes the extension to internally 3-connected graphs quite easy, as we now explain. Suppose graph G has an external separating pair (u, v).
We make use of Observation 4. Vertices u and v lie on the outer face, and their removal separates the graph into two connected components D and D . In the strictly convex drawing C of the outer face, a line segment joining u to v will separate C into two strictly convex subpolygons since by Observation 4(2) the vertices u and v are not consecutive on C. By induction, Tutte's algorithm will draw each of the two components with strictly convex faces in the appropriate subpolygon, and-in case (u, v) is not an edge of the graph-the face between D and D will also be strictly convex. Note that it is not necessary to apply Tutte's algorithm separately to the two components-one system of equations will do.
We need one more generalization of Tutte's theorem, to more general "barycenter" weights other than 1/d u . The following result is proved in [16] (or see [18]). Assign a weight w u,v > 0 to each ordered pair u, v with (u, v) ∈ E such that for each u, v w u,v = 1. Then the system of equations has a unique solution that gives a convex drawing of G with outer face C (and a strictly convex drawing of G if C is strictly convex).
We can now give an alternate proof of Hong and Nagamochi's result: Proof of Lemma 9. We must show that there is a strictly convex drawing of G with outer face C that preserves the y-coordinates of the vertices from drawing Γ. Our idea is to do this in two steps, first choosing the barycenter weights to force vertices to lie at the required y-coordinates, and then solving system (1) with these barycenter weights to determine the x-coordinates.
For the first step, we solve the following system separately for each u ∈ V I : Here the y's are the known values from Γ and the w u,v 's are variables. There are two equations and d u > 2 variables, so the system is under-determined and can easily be solved: Because Γ has y-monotone faces, every vertex u ∈ V I has neighbors below and above. Let N + u be the neighbors of u that lie above u in Γ. Let d + u = |N + u |. Similarly, let N − u be the neighbors of u that lie below u in Γ and let d − u = |N − u |. Compute the average y-coordinate of u's neighbors above and below: Observe that y u lies between y + u and y − u . Thus we can find a value t u , 0 < t u < 1, such that for v ∈ N − u , yields a solution to (2). Given values w u,v satisfying the constraints (2) for all u ∈ V I , we then solve equations (1) to find values for the x u 's. By Tutte's generalized result, this provides a strictly convex drawing of G with outer face C while preserving y coordinates.
Finally, we analyze the run-time. Our first step of finding the appropriate weights based on the y-coordinates takes linear time. As observed in [10], the system of equations (1) can be solved in O(n ω/2 ) arithmetic operations using the generalized nested dissection method of Lipton et al. [25,26] since the constraint matrix arises from a planar graph (also see [32,20,31]).

Lower Bound on the Number of Morphing Steps
In this section, we show the following lower bound on the number of required morphing steps.
There exists a drawing of an internally 3-connected graph with n vertices for which any convexifying planar morph composed of a sequence of linear morphing steps requires Ω(n) steps.
Our proof of Theorem 2 builds on the following result by Alamdari et al. [2].

Theorem 22 ([2]
). There exist two straight-line planar drawings Γ ∆ (n ) and Γ − (n ) of a path with n vertices such that any planar morph between them which is composed of a sequence of linear morphing steps requires Ω(n ) steps.
In the drawing Γ − (n ) the n vertices a 1 , . . . , a n are placed on a horizontal line with a i to the left of a i+1 for 1 ≤ i < n , see Fig. 8(a). In the drawing Γ ∆ (n ) the path forms a spiral, see Fig. 8(b). More precisely, let e i denote the edge {a i , a i+1 }. Then for each i with i mod 3 ≡ 1, the edge e i is horizontal and a i is to the left of a i+1 . For each i with i mod 3 ≡ 2, the edge e i is parallel to the line y = tan(2π/3)x and a i is to the right of a i+1 . Finally, for each i with i mod 3 ≡ 0, the edge e i is parallel to the line y = tan(−2π/3)x and a i is to the right of a i+1 .
In order to prove Theorem 2, we present a drawing Γ ∆ (n) of a cycle on n vertices which contains a subdrawing of Γ ∆ (n ) for some n ∈ Θ(n), see Fig. 8(c). The existence of a convexifying planar morph for Γ ∆ (n) with o(n) linear morphing steps would imply the existence of a planar morph Γ ∆ (n ) and Γ − (n ) with o(n ) linear morphing steps, constradicting Theorem 22.
Proof of Theorem 2. Let n = n/2 . Let Γ ∆ (n) be some planar straight-line drawing of the cycle C = (a 1 , . . . , a n , b 1 , . . . , b n−n ) such that the induced subdrawing of the path P = (a 1 , . . . , a n ) is Γ ∆ (n ). The exact realization of the path (b 1 , . . . b n−n ) is irrelevant for the purposes of this proof. We give an example in Fig. 8(c).
Assume for a contradiction that there exists a morph M composed of sequence of o(n) linear morphing steps which convexifies Γ ∆ (n). Restricting the morph M to the path P transforms Γ ∆ (n ) into a reflex chain Γ P on the boundary of a strictly convex polygon. It is easy to find O(1) additional morphing steps that transform Γ P into the drawing Γ − (n ); for example we can intermediately aim for coordinates of a 1 and a n which are extreme in some direction as in the proof of Lemma 13 (in fact, our situation here is much simpler, as we are not restricted to horizontal and vertical morphs anymore). Extending M by these additional morphs yields planar morph with o(n) ⊆ o(n ) linear morphing steps that transforms Γ ∆ (n ) into Γ − (n ). This is a contradiction to Theorem 22.

Lower Bound on Grid Size
Any 3-connected planar graph can be drawn with convex faces on a n × n grid [15] or with strictly convex faces on a O(n 2 ) × O(n 2 ) grid [5]. It would be desirable to find morphs in which Fig. 9: Illustration of small instances of the hierarchical graph family (G k ). Any convex drawing needs an exponential increase in width.
the intermediate drawings lie on a polynomial-sized grid, i.e. with a logarithmic number of bits for each vertex's coordinates. In this section we show that there is no hope of achieving this with our current approach. We design a family of examples based on those of Lin and Eades [24] to show that a single horizontal morph may unavoidably blow up the width of the drawing from O(n) to Ω(n!). Thus there is no hope of restricting to a polynomial-sized grid. A weaker goal is polynomial bit complexity. It is true that one horizontal morph causes only polynomial blow-up in the number of bits, but our algorithm uses O(n) successive steps, so there is a danger that the bit complexity required by our algorithm is exponential or worse.

Lemma 23.
There is a family (G k ) k of internally 3-connected graphs with straight-line drawings on a grid of width w(G k ) < 2k and height (G k ) = 4k for which any convex straight-line drawing preserving the y-coordinates has width w c (G k ) ≥ 4 k−1 (2k − 2)! ≈ w(G k )!
The graph G 1 is depicted in Fig. 9. Observe that G 1 has a convex drawing. The graph G k+1 is obtained from G k by introducing four new y-coordinates ("layers") and six new vertices: Introduce a C 6 as the new outerface and four more internal edges as shown in Fig. 9.
Note that G k has exactly two vertices of degree two on the outerface. It follows directly from the construction that G k has 6k + 1 vertices, 4k layers, and a straight-line-drawing of width ≤ 2k on an integer grid. It is easy to see that if G k has a convex drawing that preserves the levels of the vertices, then so does G k+1 ; we can simply shift the degree two vertices in G k and the new vertices on layers one and 4k − 1 far enough outwards.
We now argue that any convex drawing necessarily blows up the width. This follows from the following geometric observation. A similar idea was used by Lin and Eades [24] for the construction of hierarchical drawings where every straight-line drawing has a large width.

Observation 24.
Let v 0 be a vertex on level l 0 , with two neighbors u 1 and w 1 on level l 1 , u 1 has neighbor u k and w 1 has neighbor w k ; both on level l k . Denote the distance of u 1 and w 1 by d.
If the out-angles vu 1 u k and vw 1 w k are at most π, then the distance of u k and w k is at least dk.
For the convex drawings we see that w c (G 1 ) = 2. Applying Observation 24 for the topmost and bottommost vertex of the induced G k−1 in G k , it follows that w c (G 2 ) = 16, and for k ≥ 3 : w c (G k ) = ( (G k−2 ) + 2) · (G k−1 ) · w c (G k−1 ) With the recursion, the claim can be proved by induction.
Note that the family of graphs (G k ) k resulting from this construction are internally 3connected by Lemma 3 since they have a convex drawing. However, they are not 3-connected.
We can obtain the same result for 3-connected graphs simply by contracting the two degree two vertices on the outer face of G k to the top vertex.

Conclusions
We have shown how to morph any straight-line planar drawing of an internally 3-connected graph to a convex drawing while preserving planarity and increasing convexity throughout the morph. Moreover, our morph is composed of a linear number of horizontal and vertical steps, which is asymptotically optimal. The following questions are open: 1. Recall that during a convexity-increasing morph, the set of internal convex angles never decreases. We conjecture that every straight-line planar drawing of a (internally) 3connected graph admits a convexity-increasing morph to a strictly convex drawing such that during the morph the set of external reflex angles also never decreases.
2. Our algorithm for finding a convexity-increasing morph to a convex drawing can be executed in O(n 1+ω/2 ) time on a Real-RAM. Our new version of Lemma 9 also speeds up the run-time of the algorithm of Alamdari et al. [2] for morphing between two given drawings from O(n 3 ) to O(n 1+ω/2 ). For both these problems, it would be interesting to find even more efficient algorithms, or to establish non-trivial lower bounds on the run-time.
3. Design piece-wise linear morphs with a polynomial bound on the bit complexity of the intermediate drawings. This would be a step towards having intermediate drawings that lie on a polynomial-sized grid, i.e. with a logarithmic number of bits for each vertex's coordinates. This is open both for our problem of morphing to a convex drawing and for the problem of morphing between two given planar straight-line drawings.