Extending Convex Partial Drawings of Graphs

Abstract

Given a plane graph G (i.e., a planar graph with a fixed planar embedding and outer face) and a biconnected subgraph $G^{\prime }$ with a fixed planar straight-line convex drawing, we consider the question whether this drawing can be extended to a planar straight-line drawing of G. We characterize when this is possible in terms of simple necessary conditions, which we prove to be sufficient. This also leads to a linear-time testing algorithm. If a drawing extension exists, one can be computed in the same running time.

1 Introduction

The problem of extending a partial drawing of a graph to a complete one is a fundamental problem in graph drawing that has many applications, e.g., in dynamic graph drawing and graph interaction. This problem has been studied most in the planar setting and often occurs as a subproblem in the construction of planar drawings.

The earliest example of such a drawing extension result are so-called Tutte embeddings. In his seminal paper “How to Draw a Graph” [12], Tutte showed that any triconnected planar graph admits a convex drawing with its outer vertices fixed to an arbitrary convex polygon. The strong impact of this fundamental result is illustrated by its, to date, more than 850 citations and the fact that it received the “Best Fundamental Paper Award” from GD’12. The work of Tutte has been extended in several ways. In particular, it has been strengthened to only require polynomial area [5], even in the presence of collinear points [3]. Hong and Nagamochi extended the result to show that triconnected graphs admit convex drawings when their outer vertices are fixed to a star-shaped polygon [6]. For general subdrawings, the decision problem of whether a planar straight-line drawing extension exists is NP-hard [10]. Pach and Wenger [9] showed that every subdrawing of a planar graph that fixes only the vertex positions can be extended to a planar drawing with O(n) bends per edge and that this bound is tight. The drawing extension problem has also been studied in a topological setting, where edges are represented by non-crossing curves. In contrast to the straight-line variant, it can be tested in linear time whether a drawing extension of a given subdrawing exists [1]. Moreover, there is a characterization via forbidden substructures [7]. In case the topology of a straight-line drawing of a subgraph H allows a drawing extension, Timothy et al. [4] showed that there exists an extension with at most 72|V(H)| bends per edge.

In this paper, we study the problem of finding a planar straight-line drawing extension of a plane graph for which an arbitrary biconnected subgraph has been fixed in form of a planar straight-line convex drawing. The question of whether the internal faces of the subgraph can be completed have been extensively studied [3, 5, 12]. We fill the gap by studying what happens with the outer face. In particular, we study the problem of finding a planar straight-line drawing extension of a plane graph for which an arbitrary cycle has been fixed to a convex polygon. It is easy to see that a drawing extension does not always exist in this case; see Fig. 1. Let G be a plane graph and let C be a simple cycle of G drawn as a convex polygon $\varGamma _C$ in the plane. The following two simple conditions are clearly necessary for the existence of a drawing extension: (i) C has no chords that must be embedded outside of C and (ii) for every vertex v with neighbors on C that must be embedded outside of C there exists a placement of v outside $\varGamma _C$ such that the straight-line drawing of the graph induced by C and v is plane and bounded by the same cycle as in G. We show in this paper that these two conditions are in fact sufficient. Both conditions can be tested in linear time, and if they are satisfied, a corresponding drawing extension can be constructed within the same time bound (Theorem 4). This result implies a linear time algorithm to test the extendability of a planar straight-line convex drawing of a biconnected subgraph (Theorem 5).

Fig. 1

a A botanical flower with petals and stamen. (Image courtesy of Pearson Scott Foresman). b The convex polygon $\varGamma _C$ of cycle C is drawn in black. Vertices $w_{i,j}$ and $w_{l,k}$ are petals of C with $w_{l,k} \prec w_{i,j}$, vertices w and $w^{\prime }$ are stamens of $v_i$. Petal $w_{l,k}$ is realizable, whereas petal $w_{i,j}$ is not, since vertex $w_{i,j}$ cannot be placed in the plane without changing the embedding or intersecting C

Our paper starts with some necessary definitions (Sect. 2) and useful combinatorial properties (Sect. 3). Our main result is Theorem 4, the proof of which has two steps. We first show in Sect. 4 that the conditions are sufficient if $\varGamma _C$ is one-sided (i.e., it has an edge whose incident inner angles are both less than $90^\circ$). Afterward, we show in Sect. 5 that, for an arbitrary convex polygon $\varGamma _C$, we can place the neighborhood of C in such a way that the drawing is planar, and such that the boundary $C^{\prime }$ of its outer face is a one-sided polygon $\varGamma _{C^{\prime }}$. Moreover, our construction ensures that the remaining graph satisfies the conditions for extendability of $\varGamma _{C^{\prime }}$. The general result then follows directly from the one-sided case.

2 Definitions and a Necessary Condition

2.1 Plane Graphs and Subgraphs

A graph $G = (V,E)$ is planar if it has a drawing $\varGamma$ in the plane ${\mathbb {R}}^2$ without edge crossings. Drawing $\varGamma$ subdivides the plane into connected regions called faces; the unbounded region is the outer and the other regions are the inner faces. The boundary of a face is called facial cycle, and outer cycle for the outer face. The cyclic ordering of the edges around each vertex of $\varGamma$ together with the description of the outer face of $\varGamma$ characterize a class of drawings with the same combinatorial properties, which is called an embedding of G. A graph G with a planar embedding is called plane graph. A plane subgraph H of G is a subgraph of G together with a planar embedding that is the restriction of the embedding of G to H.

Let G be a plane graph and let C be a simple cycle of G. Cycle C is called strictly internal, if it does not contain any vertex of the outer face of G. A chord of C is called outer if it lies outside C in G. A cycle without outer chords is called outerchordless. The subgraph of G inside C is the plane subgraph of G that is composed of the vertices and edges of C and all vertices and edges of G that lie inside C.

2.2 Connectivity

A graph G is k-connected if the removal of any set of at most $k-1$ vertices of G does not disconnect the graph. For $k=2,3$ a k-connected graph is also called biconnected and triconnected, respectively. An internally triangulated plane graph is triconnected if and only if there is no edge connecting two non-consecutive vertices of its outer cycle (see, for example, [2]).

2.3 Star-Shaped and One-Sided Polygons

Let $\varPi$ be a polygon in the plane. Two points inside or on the boundary of $\varPi$ are mutually visible, if the open straight-line segment connecting them belongs to the interior of $\varPi$. The kernel $K(\varPi )$ of polygon $\varPi$ is the set of all the points inside $\varPi$ from which all vertices of $\varPi$ are visible. We say that $\varPi$ is star-shaped if $K(\varPi )\ne \emptyset$. We observe that, with our definition of mutual visibility, a star-shaped polygon ensures that its kernel has positive area.

A convex polygon $\varPi$ with k vertices is called one-sided, if there exists an edge e (i.e., a line segment) of $\varPi$ such that the orthogonal projection to the line supporting e maps all polygon vertices onto segment e. Then e is called the base edge of $\varPi$. Without loss of generality let $e=(v_1,v_k)$ and $v_1, \ldots , v_k$ be the clockwise ordered sequence of vertices of $\varPi$.

2.4 Extension of a Drawing

Let G be a plane graph and let H be a plane subgraph of G. Let $\varGamma _H$ be a planar straight-line drawing of H. We say that $\varGamma _H$ is extendable if drawing $\varGamma _H$ can be completed to a planar straight-line drawing $\varGamma _G$ of the plane graph G. Then $\varGamma _G$ is called an extension of $\varGamma _H$. A planar straight-line drawing of G is called convex, if every face of G (including the outer face) is represented as a convex polygon.

The following theorem by Hong and Nagamochi [6] shows the extendability of a prescribed star-shaped outer face of a plane graph.

Theorem 1

(Hong and Nagamochi [6]) Every drawing of the outer face of a triconnected planar graph G as a star-shaped polygon can be extended to a convex drawing of G. Such a drawing can be computed in linear time.

2.5 Petals and Stamens

Let G be a plane graph, and let $P_{uv}$ be a path in G between vertices u and v. Its subpath from vertex a to vertex b is denoted by $P_{uv}[a,b]$. Let C be a simple cycle of G, and let $v_1,\ldots ,v_k$ be the vertices of C in clockwise order. Given two vertices $v_i$ and $v_j$ of C, we denote by $C[v_i,v_j]$ the subpath of C encountered when we traverse C clockwise from $v_i$ to $v_j$. Assume that C is represented by a convex polygon $\varGamma _C$ in the plane. We say that a vertex $v_i$, $1\le i \le k$ of $\varGamma _C$ is flat, if $\angle v_{i-1} v_i v_{i+1} = \pi$. Throughout this paper, we assume that convex polygons do not have flat vertices.

A vertex $w\in V(G)\setminus V(C)$ adjacent to at least two vertices of C and lying outside C in G, is called a petal of C; see Fig. 1. Consider the plane subgraph $G^{\prime }$ of G induced by the vertices $V(C) \cup \{w\}$. Vertex w appears on the boundary of $G^{\prime }$ between two vertices of C, i.e., after some $v_i \in V(C)$ and before some $v_j \in V(C)$ in clockwise order. To indicate this fact, we will denote petal w by $w_{i,j}$. Edges $(w_{i,j},v_i)$ and $(w_{i,j},v_j)$ are called the outer edges of petal $w_{i,j}$. The subpath $C[v_i,v_j]$ of C is called the base of the petal $w_{i,j}$. A vertex $v_f$ is internal to petal $w_{i,j}$, if it appears on C after $v_i$ and before $v_j$ in clockwise order. A petal $w_{i,i+1}$ is called trivial. A vertex of $V(G)\setminus V(C)$ adjacent to exactly one vertex of C is called a stamen of C.

Let v be a petal of C and let u be either a petal or a stamen of C, we say that u is nested in v, and denote this fact by $u \prec v$, if u lies in the cycle delimited by the base and the outer edges of petal v. For two stamens u and v, neither $u \prec v$ nor $v\prec u$. So for each pair of stamens or petals u and v we have either $u \prec v$, or $v \prec u$, or none of these. This relation $\prec$ is a partial order. A petal or a stamen u of C is called outermost if it is maximal with respect to $\prec$.

2.6 Necessary Petal Condition

Let again G be a plane graph and let C be an outerchordless cycle of G represented by a convex polygon $\varGamma _C$ in the plane. Let $w_{i,j}$ be a petal of C. Let $G^{\prime }$ be the plane subgraph of G, induced by the vertices $V(C)\cup \{w_{i,j}\}$. We say that $w_{i,j}$ is realizable if there exists a planar drawing of $G^{\prime }$ which is an extension of $\varGamma _C$. This gives us the necessary condition that $\varGamma _C$ is extendable only if each petal of C is realizable. In the rest of the paper we prove that this condition is also sufficient.

3 Combinatorial Properties of Graphs and Petals

In this section, we derive several properties of petals in graphs, which we use throughout the construction of the drawing extension in the remaining parts of this paper. Proposition 1 allows us to restrict our attention to maximal plane graphs for which the given cycle C is strictly internal. The remaining lemmas are concerned with the structure of the (outermost) petals of C in such a graph.

Proposition 1

Let G be a plane graph on n vertices and let C be a simple outerchordless cycle of G. There exists a plane supergraph $G^{\prime }$ of G with O(n) vertices such that (i) $G^{\prime }$ is maximal plane, (ii) there are no outer chords of C in $G^{\prime }$, (iii) each petal of $G^{\prime }$ with respect to C is either trivial or has the same neighbors on C as in G, and (iv) C is strictly internal to G. Graph $G^{\prime }$ can be constructed within O(n) time.

Proof

First, we arbitrarily triangulate the graph in the interior of C. Clearly, this creates neither outer chords nor new petals. For triangulating the graph outside of C, we have to be more careful to avoid the creation of outer chords and potentially unrealizable petals. We proceed in three steps. First, we ensure that, for each edge e of C, the incident face outside of C is a triangle. In this phase, we create new petals, all of which are realizable. Second, we ensure that all faces incident to vertices of C are triangles without introducing any new petals. After this step, all faces incident to vertices of C are triangles and C is strictly internal. We then triangulate the remaining faces arbitrarily. In the following, we describe these steps in more detail and argue their correctness.

In the first step, we create, for each edge e of C, a new vertex $v_e$ that is adjacent to the endpoints of e and embed it in the face incident to e outside of C (refer to Fig. 2a). Note that each such vertex $v_e$ is a trivial petal, and it is hence realizable. Clearly, after performing this operation for each edge e of C, every face incident to an edge of C is a triangle. Note that, besides the new trivial petals, we do not create or modify any other petals. Moreover, we introduce no chords of C since any new edge is incident to a new vertex. Clearly, this step can be performed in O(|C|) time.

For the second step, we traverse all faces incident to vertices of C that are not triangles. Let f be such a face that is incident to some vertex v of C; see Fig. 2b. Notice that f can be either an inner or the outer face of G. Let (v, u) and (v, w) be the two edges incident to v that bound f. Note that (v, u) and (v, w) do not belong to C since, according to step 1, f would be a triangle in this case. Hence, since there are no outer chords of C, u and w are not in C. We create a new vertex $v_f$, connect it to u, v and w, and embed it in f. This reduces the number of non-triangular faces incident to v by 1. Note that this operation neither produces a petal nor a chord of C. After treating all faces incident to vertices of C in this way, all inner faces incident to vertices of C are triangles and C is strictly internal. This step is accomplished within time proportional to the number of non-triangular faces incident to the vertices of C, i.e., in O(n) time.

In the third step, we triangulate the remaining faces arbitrarily. None of the edges added in this step is incident to a vertex of C. Hence, this produces neither petals nor chords. Finally, if C is not strictly internal in the resulting graph, there is at most one vertex of C on the outer face. (To see this, observe that the outer face is a triangle, and if two of its vertices belong to C, the edge between them would be an outer chord, contradicting the properties of our construction.) If this case occurs, we add an additional vertex into the outer face and connect it to all three vertices of the outer face. Afterwards C is strictly internal. Again this can neither produce a petal nor an outer chord.

The resulting graph $G^{\prime }$ is triangulated and each petal of C in $G^{\prime }$ is either trivial or has the same neighbors on C as in G. Obviously, the procedure adds only O(n) vertices and runs in O(n) time. This concludes the proof. $\square$

Fig. 2

a Graph G is depicted by black, cycle C is bold. Gray vertices are added during the first step of the augmentation. b Example of an augmentation during the second step. Face f is considered, which is depicted by dashed lines. Vertex $v_f$ is added to lie inside f and connected to u, v and w. As a result v has no other incident non-triangular face

Lemma 1

Let G be an n-vertex triangulated planar graph with a strictly internal outerchordless cycle C. Then the following statements hold. (i) Each vertex of C that is not internal to an outermost petal is adjacent to two outermost petals. (ii) There is a simple cycle $C^{\prime }$ whose interior contains C and that is formed by the outermost stamens and petals of C. Finally, cycle $C^{\prime }$ can be found in O(n) time.

Proof

For (i), observe that each edge of C is incident to a triangle outside of C, whose tip then is a petal. Thus, every vertex of C is adjacent to at least two petals $p_1$ and $p_2$ such that none of them contains the other one; see Fig. 3a. For a vertex v of C that is not contained in the base of an outermost petal, this implies that there exist distinct outermost petals $p_1^{\prime }$ and $p_2^{\prime }$ with $p_1 \prec p_1^{\prime }$ and $p_2 \prec p_2^{\prime }$. Since v is not internal to any of them, it must be incident to one of the outer edges of each of them.

For (ii), let v be a vertex of C and let u and w be two stamens or petals that are adjacent in the circular ordering of neighbors around v; refer again to Fig. 3a. Then (v, u) and (v, w) together bound a face, which must be a triangle, implying that u and w are adjacent. Applying this argument to all adjacent pairs of outermost petals or stamens around C yields the claimed cycle in G that traverses exactly the outermost petals and stamens. Obviously, this construction can be carried out in O(n) time. $\square$

The following lemma is an auxiliary lemma that is only used in the proof of Lemma 3.

Lemma 2

Let G be an n-vertex triangulated planar graph with a strictly internal outerchordless cycle C. Let $u \in C$ be internal to an outermost petal v. Then there exists a chordless path from u to v that contains no other vertices of C, which can be found in O(n) time.

Fig. 3

a Illustration for the proof of Lemma 1. Cycle C is shown by bold black curve. b Illustration for the proof of Lemma 2. Cycle C is depicted by bold black. Three paths from u to v are shown by bold grey curves

Proof

If u is adjacent to v, there is nothing to prove. Otherwise, let $v_1$ and $v_2$ be the first vertex on C to the left and right of u, respectively, that are adjacent to v; see Fig. 3b. Let $C^{\prime }$ denote the cycle consisting of $C[v_1,v_2]$ and v together with two edges $(v,v_1)$ and $(v,v_2)$. The graph consisting of $C^{\prime }$ and all edges and vertices embedded inside $C^{\prime }$ is inner-triangulated and chordless, and hence triconnected. Thus, by Menger’s theorem, the graph contains three vertex-disjoint paths from u to v, which can be constructed in O(n) time [11]. The middle one of these paths cannot contain any vertices of C. We obtain the claimed path from the middle path by iteratively short-cutting it using chords. This procedure can be accomplished in time linear in the number of vertices in the path. $\square$

Lemma 3

Let G be an n-vertex maximal planar graph with a strictly internal outerchordless cycle C. Let u and v be two adjacent vertices on C that are not internal to the same petal. Then there exists a third vertex w of C such that there exist three chordless disjoint paths from u, v and w to the vertices of the outer face of G such that none of them contains other vertices of C. Such paths can be constructed in O(n) time.

Proof

Let $C_{{\mathrm {shell}}}$ denote the cycle going through the outermost petals and stamens of C, which exists by Lemma 1. It follows from Menger’s theorem that there exists a set $A = \{a,b,c\}$ of three vertices on $C_{{\mathrm {shell}}}$ that have disjoint paths to the outer face, such that none of them contains any other vertices of $C_{{\mathrm {shell}}}$. Our goal is to identify vertex w and to connect the vertices u, v, w by vertex-disjoint paths to the vertices of A such that together we obtain the claimed paths. Assume without loss of generality that v is the immediate successor of u on C in counterclockwise order.

We distinguish cases based on the number of outermost petals.

• Case 1: There are exactly two outermost petals ${{\mathbf {x}}}$ and ${{\mathbf {y}}}$. Since u and v are not both internal to the same petal, we can assume that u is in the base of petal x and v is in the base of petal y. Note further that one of u and v must be contained in the bases of both petals, and hence adjacent to them; see Fig. 4. Without loss of generality, we assume that v is. The case that u is adjacent to both of them is completely symmetric.

  Fig. 4

  

  Illustration for the proof of Lemma 3. Cycle C is solid black, cycle $C_{{\mathrm {shell}}}$ is solid blue. Edges incident to petals are dashed. The identified paths are bold gray. a Case 1a: Vertex b is contained in the counterclockwise path from x to y. b–c Case 1b: Vertex b is contained in the clockwise path from x to y (Color figure online)

  We consider the subpaths of $C_{{\mathrm {shell}}}$ from x to y. At least one of them contains a vertex of A in its interior. If one of them contains all three of them in its interior, let b denote the middle one, otherwise, let b denote an arbitrary one. Let a and c denote the vertices of $A \setminus \{b\}$ that occur before and after b in counterclockwise direction along $C_{{\mathrm {shell}}}$.

  We distinguish cases based on whether b is contained in the clockwise or in the counterclockwise path from x to y.

• Case 1a: Vertex ${{\mathbf {b}}}$ is contained in the counterclockwise path from ${{\mathbf {x}}}$ to ${{\mathbf {y}}}$. See Fig. 4a for an illustration. It then follows that b is a stamen of v. We choose w as an arbitrary vertex in the base of petal y such that it is distinct from u and v (note that this is always possible since C has length at least 3).

  Now the claimed paths can be constructed as follows. For u, take the path from u to x (Lemma 2), and from there along $C_{{\mathrm {shell}}}$ to a, avoiding b. For v, take the edge (v, b). For w, take the path from w to y (Lemma 2), and from there along $C_{{\mathrm {shell}}}$ to c, avoiding b. It follows from the choice of b that these paths are disjoint.

• Case 1b: Vertex ${{\mathbf {b}}}$ is contained in the clockwise path from ${{\mathbf {x}}}$ to ${{\mathbf {y}}}$. Then b must be a stamen that is, by construction, not adjacent to v.

  If b is not adjacent to u, choose b’s unique neighbor on C as w; see Fig. 4b. The paths are constructed as follows. For u, take the path from u to x, as guaranteed by Lemma 2, and from there to c, avoiding b. For v, take the edge (v, y) and from there to a, avoiding b. For w, take the edge (w, b). It follows from the choice of b that the constructed paths are vertex disjoint.

  Otherwise b is adjacent to u; see Fig. 4c. Then choose w as a vertex that lies on C counterclockwise between u and v. Such a vertex exists, since C contains at least three vertices. The paths are constructed as follows. For u, we take the edge (u, b). For v, we take the edge (v, x) and the path from x along $C_{{\mathrm {shell}}}$ to c, avoiding b. For w, we take the path from w to y (Lemma 2) and from there to a, avoiding b. Again, it follows from the choice of b that the constructed paths are vertex disjoint.

• Case 2: There are at least three outermost petals of ${{\mathbf {C}}}$. See Fig. 5 for the illustration of this case. By the conditions of the Lemma, vertices u and v are not internal to the same petal. Since u and v are adjacent, at most one of them is internal to a petal. Without loss of generality assume that v is not internal to a petal, and let x and y denote the two outermost petals adjacent to v, such that u is in the base of petal x. One of the two subpaths of $C_{{\mathrm {shell}}}$ connecting x and y contains in its interior a vertex of A. If there are three vertices of A in the interior of one of these paths, let b denote the middle one, otherwise, let b denote an arbitrary one. The vertices of A before and after it in counterclockwise direction along $C_{{\mathrm {shell}}}$ are a and c, respectively.

  Fig. 5

  

  Illustration for the proof of Lemma 3. Cycle C is solid black, cycle $C_{{\mathrm {shell}}}$ is solid blue. Edges incident to petals are dashed. The identified paths are bold gray. a Case 2a: b–c Case 2b:

  We distinguish cases based on whether b is contained in the clockwise or in the counterclockwise path from x to y along $C_{{\mathrm {shell}}}$.

• Case 2a: Vertex ${{\mathbf {b}}}$ is in the counterclockwise path from ${{\mathbf {x}}}$ to ${{\mathbf {y}}}$ along ${{\mathbf {C}}}_{\mathbf{shell}}$.

  Then, b is a stamen adjacent to v by the choice of x and y; see Fig. 5a. Let w be any vertex adjacent to y but distinct from v. Note that $w \ne u$ by the assumption that there are at least three petals. We construct the following paths. For u, we apply Lemma 2 to construct a path from u to x and then follow $C_{{\mathrm {shell}}}$ to a, avoiding b. For v, we take the edge vb. Finally, for w, we take the edge wy and then traverse $C_{{\mathrm {shell}}}$ to c, avoiding b. Note that the paths are disjoint by the choice of b.

• Case 2b: Vertex ${{\mathbf {b}}}$ is in the clockwise path from ${{\mathbf {x}}}$ to ${{\mathbf {y}}}$ along ${{\mathbf {C}}}_{\mathbf{shell}}$. Then, b is a petal or a stamen but, by definition, not adjacent to v. If b is adjacent to a vertex that is distinct from u as well, then we choose this vertex as w; see Fig. 5b. For w, we take as path the edge wb. We use the path from u to x to c (along $C_{{\mathrm {shell}}}$) and the path from v to y to a as above.

  If b is adjacent to u (Fig. 5c), then pick w as a vertex adjacent to y but distinct from u and v (such a vertex exists since petal y has at least two neighbors on C, and since there are at least three petals). Then the paths are ub, the path from v to x to c and from w to y to a. As above the paths can be chosen such that they are disjoint.

In all cases, if a path contains chords, we iteratively short-cut it by using chords. In this way we obtain the three chordless paths. The time complexity of the construction is bounded by: an application of Lemma 1, which takes O(n) time; an application of Menger’s theorem, which can be accomplished in time linear in the number of vertices [11]; and finally, a constant number of applications of Lemma 2, each of which takes linear lime. Thus, we infer that the overall construction takes O(n) time. $\square$

4 Extension of a One-Sided Polygon

Let G be a plane graph, and let C be a simple outerchordless cycle, represented by a one-sided polygon $\varGamma _C$. In this section, we show that if each petal of C is realizable, then $\varGamma _C$ is extendable to a straight-line drawing of G. This result serves as a tool for the general case, which is shown in Sect. 5.

The drawing extension we produce preserves the outer face, i.e., if the extension exists, then it has the same outer face as G. It is worth mentioning that, if we are allowed to change the outer face, the proof becomes rather simple, as the following theorem shows.

Theorem 2

Let G be a maximal plane graph and let C be an outerchordless cycle of G, represented in the plane by a one-sided polygon $\varGamma _C$. Then, for a suitable choice of the outer face of G, the drawing $\varGamma _C$ is extendable.

Proof

Let $(v_1,v_k)$ be the base edge of $\varGamma _C$. Edge $(v_1,v_k)$ is incident to two faces of G, to a face $f_{{\mathrm {in}}}$ inside C and to a face $f_{{\mathrm {out}}}$ outside C. We select $f_{{\mathrm {out}}}$ as the outer face of G. With this choice, edge $(v_1,v_k)$ is on the outer face of G. Let v be the third vertex of this face. We place the vertex v far enough from $\varGamma _C$, so that all vertices of $\varGamma _C$ are visible from v. Thus, we obtain a planar straight-line drawing of the subgraph $G_v$ induced by the vertices $V(C) \cup \{v\}$ such that each face is represented by a star-shaped polygon. Each subgraph of G inside a face of $G_v$ is triconnected, and therefore, we can complete the existing drawing to a straight-line planar drawing of G, by Theorem 1. $\square$

In the rest of the section we show that extendability of $\varGamma _C$ can be efficiently tested, even if the outer face of G has to be preserved. The following simple geometric fact will be used in the proof of the result of this section; see Fig. 6 for an illustration.

Fact 1

Let pqrt be a convex quadrilateral and let o be the intersection of its diagonals. Let $S_{pt}$ be a one-sided convex polygon with base $\overline{pt}$, that lies inside triangle $\triangle opt$. Let $\overline{ab}$ and $\overline{cd}$ be such that $b,d \in S_{pt}$, ordered clockwise as t, d, b, p and $a,c \in \overline{qr}$, ordered as q, a, c, r. Then, neither $\overline{ab}$ and $\overline{cd}$ intersect each other, nor do they intersect a segment between two consecutive points of $S_{pt}$.

Fig. 6

Illustration of Fact 1. Points of the set $S_{pt}$ are black. Neither segments $\overline{ab}$ and $\overline{cd}$ intersect each other, nor do they intersect a segment between two consecutive points of $S_{pt}$

We are now ready to prove the main result of this section.

Theorem 3

Let G be a n-vertex plane graph and C be a simple outerchordless cycle of G, represented in the plane by a one-sided polygon $\varGamma _C$. If every petal of C is realizable, then $\varGamma _C$ is extendable. If it exists, such an extension can be constructed in O(n) time.

Proof

For the following construction we need to ensure that G is a maximal plane graph and cycle C is strictly internal. If this is not the case, we apply Proposition 1, to complete G to a maximal plane graph, where C is strictly internal. For simplicity of notation, we refer to the new graph as G. Notice that the application of Proposition 1 only introduces trivial, and therefore realizable, petals. Moreover, no outer chord is introduced. After the construction of the extension of C, we remove the vertices and edges added by the application of Proposition 1.

Let $v_1,\ldots ,v_k$ be the clockwise ordering of the vertices of C, so that $(v_1,v_k)$ is the base of $\varGamma _C$. We rotate $\varGamma _C$ so that $(v_1,v_k)$ is horizontal. Let a, b, c be the vertices of the outer face of G in clockwise order; see Fig. 7. By Lemma 3, there exists a vertex $v_j$, $1<j<k$, such that there exist chordless disjoint paths between $v_1,v_j,v_k$, and the vertices a, b, c, respectively. Denote these paths by $P_{v_1a}$, $P_{v_jb}$ and $P_{v_kc}$. Some vertices of $P_{v_1a}$ and $P_{v_kc}$ are possibly adjacent to each other, as well as to the boundary of C. Depending on these adjacencies, we show how to draw the paths $P_{v_1a}$, $P_{v_kc}$ and how to place vertex b, so that the graph induced by these vertices and cycle C is drawn with star-shaped faces. Then, the drawing of G can be completed by applying Theorem 1.

Let $v_i$ be the topmost vertex of $\varGamma _C$. It can happen that there are two adjacent topmost vertices $v_i$ and $v_{i+1}$. However, $v_{i-1}$ and $v_{i+2}$ have a smaller y-coordinate, since $\varGamma _C$ does not contain flat vertices. In the following, we assume that $v_{i}$ and $v_{i+1}$ have the same y-coordinate. The case when $v_i$ is unique can be seen as a special case where $v_i=v_{i+1}$. Without loss of generality assume that $i+1\le j \le k-1$, the case where $2\le j \le i$ is treated symmetrically. Notice that the presence of the path $P_{v_jb}$ ensures that edges between vertices of $P_{v_1a}$ and $P_{v_kc}$ can only lie in the interior of the cycle delimited by these paths and edges $(v_1,v_k)$ and (a, c); refer to Fig. 7. Consider a vertex of $P_{v_1a}$ that is a petal of C. The base of such a petal cannot contain edge $(v_{k-1},v_k)$, since this would cause a crossing with $P_{v_kc}$. Moreover, if the base of this petal contains edge $(v_1,v_k)$, then it cannot contain any edge $(v_f,v_{f+1})$ for $i\le f < j$, since otherwise this petal would not be realizable. Thus a vertex of $P_{v_1a}$ is either adjacent to $v_k$ or to a vertex $v_f$, where $i+1 \le f \le j$, but not both. It is worth mentioning that a vertex of $P_{v_1a}$ cannot be adjacent to any $v_f$, $j+1 \le f\le k-1$, since such an adjacency would cause a crossing either with $P_{v_jb}$ or with $P_{v_kc}$.

Fig. 7

Illustration for the proof of Theorem 3. Edges between $C[v_1,v_i]$ and $P_{v_1a}[v_1,w^{\prime }]\cup \{v_k\}$ are gray. Edges between $C[v_{i+1},v_j]$ and $P_{v_1a}[w,a]$ are dashed

Fig. 8

Illustration for the proof of Theorem 3. For space reasons lines are shown by curves

Let s, $\ell$ and $\ell _c$ be three distinct lines through $v_j$ that lie clockwise between the slopes of edges $(v_{j-1},v_j)$ and $(v_j,v_{j+1})$; see Fig. 8. Such lines exist since $\varGamma _C$ does not contain flat vertices. Let $\ell _i$ be the line through $v_i$ with the slope of $(v_{i-1},v_i)$. Let $\ell _a$ be the half-line originating at an internal point of $(v_1,v_k)$ towards $-\infty$, slightly rotated counterclockwise from the horizontal position, so that it crosses $\ell _i$. Let q denote the intersection point of $\ell _a$ and $\ell _i$. Let p be any point on $\ell _a$ to the left of q. Let $\ell _a^{\prime }$ be the line through p with the slope of $\ell$. By construction of lines s, $\ell$ and $\ell _c$, line $\ell _a^{\prime }$ crosses s above the polygon $\varGamma _C$ at point $p_a$ and line $\ell _c$ below this polygon at point $p_c$.

Let $G^{\prime }$ be the plane subgraph of G induced by the vertices of C, $P_{v_1a}$, and $P_{v_kc}$. The outer cycle of $G^{\prime }$ consists of edge (a, c) and a path $P_{ac}$ between vertices a and c.

Claim 1

The vertices of $P_{v_1a}$ and $P_{v_kc}$ can be placed on lines $\ell _a$, $\ell _a^{\prime }$ and $\ell _c$ such that the resulting straight-line drawing of $G^{\prime }$ is planar, path $P_{ac}$ is represented by an x-monotone polygonal chain, and the inner faces of $G^{\prime }$ are star-shaped polygons.

The vertices of $P_{v_1a}$ will be placed on line $\ell _a$ between points p and q and on line $\ell _a^{\prime }$ above point $p_a$. The vertices of $P_{v_kc}$ will be placed on $\ell _c$ below $p_c$. In order to place the vertices, we need to understand how the vertices of $P_{v_1a}$ are adjacent to vertices of C. As we travel on $P_{v_1a}$ from $v_1$ to a, we first meet all vertices adjacent to $v_1,\ldots ,v_i$ and then all vertices adjacent to $v_{i+1},\ldots ,v_j$, since G is a planar graph. Let w be the first vertex of $P_{v_1a}$ adjacent to $v_{f}$, $i+1 \le f \le j$, and let $w^{\prime }$ be the vertex preceding w on $P_{v_1a}$. We place vertices of $P_{v_1a}[v_1,w^{\prime }]$, in the order they appear in the path, on line $\ell _a$, between q and p, in increasing distance from $v_1$. We place all vertices of $P_{v_1a}[w,a]$ on $\ell _a^{\prime }$ above $p_a$ in increasing distance from p. We draw the edges between the vertices of C and $P_{v_1a}$. Notice that vertex w might not exist, since it might happen that none of the vertices of $P_{v_1a}$ is adjacent to $v_{f}$, $i+1 \le f \le k$. In this case all vertices of $P_{v_1a}$ are placed on line $\ell _a$, between q and p.

In the following, we show that the constructed drawing is planar. Notice that the quadrilateral formed by the points $w,a,v_j,v_{i+1}$ is convex, by the choice of line $\ell _a^{\prime }$ and the positions of vertices w and a on it. Also, notice that the points of vertices $v_{i+1},\ldots ,v_j$ form a one-sided polygon with base segment $\overline{v_{i+1}v_j}$, which lies in the triangle $\triangle ov_jv_{i+1}$, where o is the intersection of $\overline{v_{i+1}a}$ and $\overline{v_{j}w}$. Thus, by Fact 1, the edges connecting $C[v_{i+1},v_j]$ and $P_{v_1a}[w,a]$ do not cross each other. By applying Fact 1, we can also prove that edges connecting $P_{v_1a}[v_1,w^{\prime }]$ with $C[v_1,v_i]$, cross neither each other, nor $\varGamma _C$. Recalling that vertices of $P_{v_1a}[v_1,w^{\prime }]$ can be also adjacent to $v_k$, we notice that these edges also do not cross $\varGamma _C$, by the choice of line $\ell _a$. Finally, path $P_{v_1a}$ is chordless, and therefore the current drawing is planar. Notice that the subpath of $P_{a,c}$ that has already been drawn is represented by an x-monotone chain. We next draw the vertices of $P_{v_kc}$. We observe that in the already constructed drawing path $P_{v_1a}$ taken together with edge $(v_1,v_k)$ is represented by an x-monotone chain, each point of which is visible from any point below the line $\ell _a^{\prime }$. This means that any point below line $\ell _a^{\prime }$, can be connected by a straight-line segment to the vertices $V(P_{v_1a}) \cup \{v_k\}$ without creating any crossing either with $P_{v_1a}$ or with $(v_1,v_k)$. We also notice that any of the vertices $v_j,\ldots ,v_k$ can be connected to a point of $\ell _c$, without intersecting $\varGamma _C$. Recall that $p_c$ denotes the intersection point of $\ell _c$ and $\ell _a^{\prime }$. Thus we place the vertices of $P_{v_kc}$ on the line $\ell _c$, below $\ell _a^{\prime }$, in increasing distance from point $p_c$. Applying Fact 1 we can prove that the edges induced by $\{v_j,\ldots ,v_k\} \cup V(P_{v_kc})$ are drawn without crossings. Edges between $P_{v_kc}$ and $P_{v_1a}$ cross neither $P_{v_1a}$, nor $(v_1,v_k)$ by the choice of lines $\ell _c$ and $\ell _a^{\prime }$.

We have constructed a planar straight-line drawing of $G^{\prime }$. We notice that path $P_{ac}$ is drawn as an x-monotone polygonal chain. We also notice that the faces of $G^{\prime }$, created when placing vertices of $P_{v_1a}$ (resp. $P_{v_kc}$) are star-shaped and have their kernels arbitrarily close to the vertices of $P_{v_1a}$ (resp. $P_{v_kc}$). This concludes the proof of the claim.

We now extend the constructed drawing of $G^{\prime }$ to a drawing of G. Notice that vertex b is possibly adjacent to some of the vertices of $P_{ac}$. Thus, placing b at an appropriate distance above $P_{ac}$, the edges between b and $P_{ac}$ can be drawn straight-line without intersecting $P_{ac}$ and therefore no other edge of $G^{\prime }$. The faces created when placing b are star-shaped and have their kernels arbitrarily close to b. We finally apply Theorem 1.

The time complexity of the described construction is determined by: an application of Proposition 1, after which the number of vertices in the graph is still O(n); an application of Lemma 3; the construction of a constant number of lines; a constant number of line-line intersections; a linear number of vertices and edges traversed and drawn on the plane; and finally, by multiple applications of Theorem 1, each of which requires time linear in the size of the subgraph it affects.

5 Main Theorem

Let G be a maximal plane graph and C be a strictly internal simple outerchordless cycle of G, represented by an arbitrary convex polygon $\varGamma _C$ in the plane. In Theorem 4 we prove that it is still true that if each petal of C is realizable, then $\varGamma _C$ is extendable. Before stating and proving Theorem 4, we introduce notation that will be used through this section.

Recall that $v_1,\ldots ,v_k$ denote the vertices of C. Let $w_{i,j}$ be an outermost petal of C in G. Let $\ell _i$ (resp. $\ell _j$) be a half-line originating at $v_i$ (resp. $v_j$) and passing through $v_{i+1}$ (resp. $v_{j-1}$); see Fig. 9a. Since $w_{i,j}$ is realizable, lines $\ell _i$ and $\ell _j$ intersect. Denote by ${\mathrm {apex}}(w_{i,j})$ their intersection point and by ${\mathrm {cone}}(w_{i,j})$ the subset of $\mathbb {R}^2$ that is obtained by the intersection of the half-planes defined by $\ell _i$ and $\ell _j$, not containing $\varGamma _C$. It is clear that any internal point of ${\mathrm {cone}}(w_{i,j})$ is appropriate to draw $w_{i,j}$ so that the plane subgraph of G induced by $V(C) \cup \{w_{i,j}\}$ is crossing-free. For consistency, we also define ${\mathrm {cone}}(w)$ and ${\mathrm {apex}}(w)$ of an outer stamen w of C as follows. Assume that w is adjacent to $v_i \in C$. Then ${\mathrm {cone}}(w) \subset \mathbb {R}^2$ is the union of the half-planes defined by lines of edges $(v_{i-1},v_i)$ and $(v_i,v_{i+1})$, that do not contain $\varGamma _C$. We set ${\mathrm {apex}}(w)=v_i$.

Fig. 9

a Vertex $w_{i,j}$ is the petal of C with base $C[v_i,v_j]$. Point ${\mathrm {apex}}(w_{i,j})$ is red, region ${\mathrm {cone}}(w_{i,j})$ is gray. Vertex w is a stamen of $v_{j+1}$. The union of the half-planes defined by lines of edges $(v_{j},v_{j+1})$ and $(v_{j+1},v_{j+2})$ is ${\mathrm {cone}}(w)$. Point ${\mathrm {apex}}(w)$ is blue. b Graph $G_{{\mathrm {shell}}}$. Polygon $\varGamma _C$ is black. Cycle $C_{{\mathrm {shell}}}$ is bold. Cycle $C_{{\mathrm {shell}}}'$ is blue. Graph $G_{{\mathrm {shell}}}'$ is comprised by blue, red and black edges. Vertices of B are squares (Color figure online)

Let P (resp. S) denote the set of outermost petals (resp. stamens) of C in G. By Lemma 1, there exists a cycle $C_{{\mathrm {shell}}}$ in G that contains exactly $P \cup S$. Let $G_{{\mathrm {shell}}}$ denote the plane subgraph of G induced by the vertices of C and $C_{{\mathrm {shell}}}$; see Fig. 9b. Let $C_{{\mathrm {shell}}}'$ denote the outer cycle of $G_{{\mathrm {shell}}}$. We denote the graph consisting of C, $C_{{\mathrm {shell}}}'$ and edges between them by $G_{{\mathrm {shell}}}'$. Each petal or stamen of C, say w, that belongs to $C_{{\mathrm {shell}}}$ but not to $C_{{\mathrm {shell}}}'$, belongs to a face of $G_{{\mathrm {shell}}}'$. We denote this face by ${\mathrm {shell}}(w)$. We categorize the faces of $G_{{\mathrm {shell}}}$ as follows. The faces that lie inside cycle C are called faces of C. The faces that are bounded only by $C_{{\mathrm {shell}}}$ and its chords, are called faces of $C_{{\mathrm {shell}}}$. Notice that each face of $C_{{\mathrm {shell}}}$ is a triangle. Notice that a face of $G_{{\mathrm {shell}}}$ that is comprised by two consecutive edges adjacent to the same vertex of C (not belonging to C), is a triangle, and contains no vertex of $G \setminus G_{{\mathrm {shell}}}$, since both facts would imply that the taken edges are not consecutive. Finally, faces bounded by a subpath of C and two edges adjacent to the same petal, are called petal faces. The plane subgraph of G inside a petal face is triangulated and does not have a chord connecting two vertices of its outer face, and therefore is triconnected. Thus we have the following

Observation 1

Each vertex of $G \setminus G_{{\mathrm {shell}}}$ either lies in a face of C, or in a face that is a triangle, or in a petal face, or outside $C^{\prime }_{{\mathrm {shell}}}$. Each subgraph of G inside a petal face is triconnected.

Theorem 4

Let G be an n-vertex plane graph and let C be a simple outerchordless cycle of G, represented by a convex polygon $\varGamma _C$ in the plane. The drawing $\varGamma _C$ is extendable to a straight-line drawing of G if and only if each petal of C is realizable. Both, testing the condition and the construction of an extension can be accomplished in O(n) time.

Proof

The condition that each petal of C is realizable is clearly necessary. Next we show that it is also sufficient.

Assume that each petal of C is realizable. Similarly to the proof of Theorem 3, we first complete G to a maximal plane graph, such that cycle C becomes strictly internal, by applying Proposition 1. The new maximal plane graph (for simplicity of notation denoted also by G) contains no outer chord and only realizable petals, since the newly added petals are trivial. When the construction of the extension of C is completed, we simply remove the vertices and edges added by Proposition 1.

We first show how to draw the graph $G^{\prime }_{{\mathrm {shell}}}$. Afterward we complete it to a drawing of $G_{{\mathrm {shell}}}$. Our target is to represent $C^{\prime }_{{\mathrm {shell}}}$ as a one-sided polygon, so that Theorem 3 can be applied for the rest of G that lies outside $C^{\prime }_{{\mathrm {shell}}}$.

Claim 2

Polygon $\varGamma _C$ can be extended to a straight-line drawing of graph $G^{\prime }_{{\mathrm {shell}}}$ where its outer face $C^{\prime }_{{\mathrm {shell}}}$ is represented by a one-sided polygon such that each petal of $C^{\prime }_{{\mathrm {shell}}}$ is realizable. Moreover, $C^{\prime }_{{\mathrm {shell}}}$ contains in its interior all points of $\{{\mathrm {apex}}(w)\mid w \in C_{{\mathrm {shell}}} \}$.

Proof

Recall that P (resp. S) denotes the set of outermost petals (resp. stamens) of C in G. Let B denote the set of vertices of C, to which stamens $S \cap C^{\prime }_{{\mathrm {shell}}}$ are adjacent; refer to Fig. 9b. By construction of the ${\mathrm {apex}}$ points, the set $\{ {\mathrm {apex}}(w) \mid w \in P \cap C^{\prime }_{{\mathrm {shell}}}\} \cup B$ is in convex position, and we denote by $\varPi$ its convex hull; refer to Fig. 10a. Polygon $\varPi$ may be degenerate, and may contain only a single vertex or a single edge. We treat these cases separately to complete the construction of the drawing of the graph $G^{\prime }_{{\mathrm {shell}}}$.

• Case 1: Polygon $\varPi$ is non-degenerate. Let p be a point inside $\varPi$. Let $\ell (w)$ denote a half-line from p through w, where w is a vertex of $\varPi$. If we order the constructed half-lines around p, any two consecutive lines have between them an angle less than $\pi$. If $w \in B$, we substitute $\ell (w)$ by the same number of slightly rotated lines as the number of stamens of $C^{\prime }_{{\mathrm {shell}}}$ adjacent to w, without destroying the order; refer to Fig. 10a. Thus, for each $w\in C^{\prime }_{{\mathrm {shell}}}$, a line $\ell (w)$ is defined. Notice that, for any $w \in P \cap C^{\prime }_{{\mathrm {shell}}}$, line $\ell (w)$ passes through ${\mathrm {apex}}(w)$, and the infinite part of $\ell (w)$ lies in ${\mathrm {cone}}(w)$. Thus, for any position of w on a point of $\ell (w) \cap {\mathrm {cone}}(w)$, edges between C and w do not cross $\varGamma _C$. For a stamen $w \in S \cap C^{\prime }_{{\mathrm {shell}}}$, line $\ell (w)$ crosses ${\mathrm {cone}}(w)$ very close to ${\mathrm {apex}}(w)$, and its infinite part lies in ${\mathrm {cone}}(w)$. Thus, similarly, for any position of w on a point of $\ell (w) \cap {\mathrm {cone}}(w)$, edges between C and w do not cross $\varGamma _C$.

  Fig. 10

  

  a Construction of drawing of graph $G_{{\mathrm {shell}}}$ shown in Fig. 9b. Apex points are gray, points of B are black squares. Polygon $\varPi$ is bold gray, lines $\{\ell (w) \mid w\in C^{\prime }_{{\mathrm {shell}}}\}$ are dashed gray. b Choice of the base for the one-sided polygon representing $C^{\prime }_{{\mathrm {shell}}}$. Angle of petal w is large, thus none of the edges in the base of w is chosen as the base edge. Edge $e=(u,v)$ is a possible choice for the base edge

  We next decide which edge of $C^{\prime }_{{\mathrm {shell}}}$ to “stretch”, i.e., which edge will serve as the base edge of the one-sided polygon representing $C^{\prime }_{{\mathrm {shell}}}$. In order to be able to apply Theorem 3, this one-sided polygon must be such that each petal of $C^{\prime }_{{\mathrm {shell}}}$ is realizable. Thus we choose the base edge e of $C^{\prime }_{{\mathrm {shell}}}$ as follows; refer to Fig. 10b. Let w be a petal of $C^{\prime }_{{\mathrm {shell}}}$ and let (w, p), (w, q) be the outer edges of petal w. Consider the lines $\ell (p)$ and $\ell (q)$, and the angle between them that contains ${\mathrm {apex}}(w)$, we call it angle of petal w. Observe that there exists at most one petal (called large petal) of $C^{\prime }_{{\mathrm {shell}}}$ whose angle is greater than $\pi$. Let $e=(u,v)$ be any edge of $C^{\prime }_{{\mathrm {shell}}}$ such that (1) e does not belong to the base of a large petal (such an edge exists, since there are no double edges in G) and (2) if e belongs to the base of some petal, then at least one of u, v is adjacent to an outermost petal of $C^{\prime }_{{\mathrm {shell}}}$.

  The edge $e=(u,v)$, identified in the previous paragraph, will serve as the base of the one-sided polygon, which we are going to construct next. Recall that $\ell (u)$ and $\ell (v)$ are consecutive in the sequence of half-lines we have constructed. Let $\kappa$ be a circle around $\varGamma _C$ that contains in the interior the polygon $\varPi$ and the set of points $\{{\mathrm {apex}}(w) \mid w\in C_{{\mathrm {shell}}}\}$. Let $\ell$ be a half-line bisecting the angle between $\ell (u)$ and $\ell (v)$ (refer to Fig. 11). Let $\lambda$ be a parabola with $\ell$ as axis of symmetry and the center of $\kappa$ as focus. We position and parametrize $\lambda$ such that it does not cross $\ell$ and $\kappa$.

  With this placement of $\lambda$, each half-line $\ell (w)$, $w \in \varPi$, crosses $\lambda$, moreover, intersections with $\ell (u)$ and $\ell (v)$ are on different branches of $\lambda$ and are the last ones as we walk on $\lambda$ from its origin to infinity. Let $\varPi ^{\prime }$ be the convex polygon comprised by the intersection points of lines $\{\ell (w) \mid w\in V(C^{\prime }_{{\mathrm {shell}}})\}$ with $\lambda$. Notice that $\varPi ^{\prime }$ is a one-sided polygon with the base edge $e=(u,v)$. We scale $\varPi ^{\prime }$ with respect to the center of $\kappa$ so that $\varPi ^{\prime }$ contains the circle $\kappa$ in the interior. The minimum scale factor is determined by the segment of $\varPi ^{\prime }$ that is closest to the center of $\kappa$. As a result, for each $w \in C$, ${\mathrm {cone}}(w) \cap \varPi ^{\prime }_{{\mathrm {in}}} \ne \emptyset$, where $\varPi ^{\prime }_{{\mathrm {in}}}$ denotes the interior of $\varPi ^{\prime }$.

  We next show that each petal of $C_{{\mathrm {shell}}^{\prime }}$ is realizable by the choice of edge e. Thus, if e does not belong to the base of a petal of $C^{\prime }_{{\mathrm {shell}}}$, then all petals of $C^{\prime }_{{\mathrm {shell}}}$ are realizable. Otherwise, $e=(u,v)$ belongs to the base of an outermost petal w of $C^{\prime }_{{\mathrm {shell}}}$, and is chosen such that either (u, w) or (v, w) exists and represents an outer edge of w. Recall that w is not a large petal, thus, the angle between the lines $\ell (u)$ and $\ell (v)$ is at most $\pi$. Since $\varPi ^{\prime }$ is a one-sided polygon with the base edge (u, v), petal w is realizable. Since w is an outermost petal of $C^{\prime }_{{\mathrm {shell}}}$, we infer that all the remaining petals containing e in their base are also realizable. This concludes the proof of the claim in the non-degenerate case.

• Case 2: Polygon $\varPi$ is degenerate and has two vertices. Notice that in this case cycle $C^{\prime }_{{\mathrm {shell}}}$ contains at most two petals, since each petal of $C^{\prime }_{{\mathrm {shell}}}$ is a vertex of $\varPi$. Assume that $C^{\prime }_{{\mathrm {shell}}}$ contains two petals, w and $w^{\prime }$. Since $C^{\prime }_{{\mathrm {shell}}}$ contains at least three vertices (G does not have double edges), there would be at least one stamen $w^{\prime \prime }$ in $C^{\prime }_{{\mathrm {shell}}}$. However, the vertex of C, to which $w^{\prime \prime }$ is adjacent, together with w and $w^{\prime }$, contribute three vertices to $\varPi$, which is a contradiction to the assumption that $\varPi$ has two vertices. Thus, in this case $C^{\prime }_{{\mathrm {shell}}}$ contains at most one petal of C. In the following we consider two subcases, first when $C^{\prime }_{{\mathrm {shell}}}$ contains one petal, and second when it contains no petal.

• Case 2.a: $C^{\prime }_{{\mathrm {shell}}}$ contains a petal w of C (Fig. 12a). Notice that there are at least two stamens of C in $C^{\prime }_{{\mathrm {shell}}}$, since otherwise $C^{\prime }_{{\mathrm {shell}}}$ would contain only two vertices, and therefore there would be a double edge in G. Moreover, all stamens of C that are in $C^{\prime }_{{\mathrm {shell}}}$, are adjacent to the same vertex $v_i$ of C. Let $s_1,\ldots ,s_k$ be the stamens adjacent to $v_i$, appearing clockwise in $C^{\prime }_{{\mathrm {shell}}}$. Let $\ell (s_k)$ be a line through $v_i$ that does not cross $\varGamma _C$; see Fig. 13a. There exists a half-line $\ell (w)$ in ${\mathrm {cone}}(w)$ that does not cross $\ell (s_k)$. Let $\ell (s_1)$ be a half-line through $v_i$, lying in the half-plane defined by $\ell (s_k)$ not containing $\varGamma _C$, slightly rotated clockwise. Let $\ell (s_2),\ldots ,\ell (s_{k-1})$ be lines through $v_i$ that lie clockwise between $\ell (s_1)$ and $\ell (s_k)$. The angle between two consecutive half-lines $\ell (s_1),\ldots ,\ell (s_k), \ell (w)$ is less than $\pi$. Moreover, each of the half-lines has its infinite part in the corresponding cone. Moreover, for any position of w (resp. $s_i$) on a point of $\ell (w) \cap {\mathrm {cone}}(w)$ (resp. $\ell (s_i) \cap {\mathrm {cone}}(s_i)$), edges between C and w (resp. $s_i$) do not cross $\varGamma _C$. Thus, we can choose base edge e and then apply a construction using circle $\kappa$ and parabola $\lambda$ identical to the case when polygon $\varPi$ is not degenerate.

• Case 2.b: $C^{\prime }_{{\mathrm {shell}}}$ does not contain any petal of C (Fig. 12b). In this case $C^{\prime }_{{\mathrm {shell}}}$ contains at least three stamens of C, and all of them are adjacent to two vertices of C, say $v_i$ and $v_j$, otherwise $\varPi$ would contain more than two vertices. Without loss of generality assume that at least two stamens of C are adjacent to $v_i$. Let them be $s_1,\ldots ,s_k$. Let $t_1,\ldots ,t_p$ be the stamens adjacent to $v_j$. The construction of half-lines $\ell (s_1),\ldots , \ell (s_k),\ell (t_1),\ldots ,\ell (t_p)$ can be done analogous to Case 2.a, where line $\ell (w)$ is substituted by a set of closely placed lines $\ell (t_1),\ldots ,\ell (t_p)$. Since the angle between two consecutive half-lines $\ell (s_1),\ldots , \ell (s_k)$, $\ell (t_1),\ldots ,\ell (t_p)$ is less than $\pi$, we proceed again as in the non-degenerate case.

• Case 3: Polygon $\varPi$ is degenerated and has a single vertex (Fig. 12c). We first notice that in this case $C^{\prime }_{{\mathrm {shell}}}$ does not contain any petal of C. This is because $C^{\prime }_{{\mathrm {shell}}}$ contains at least one stamen of C, adjacent to a vertex $v_i$ of C. Thus a petal together with $v_i$ would contribute two vertices to $\varPi$. Therefore, $C^{\prime }_{{\mathrm {shell}}}$ contains only stamens of C. These stamens are adjacent to a single vertex of C, say $v_i$, since otherwise $\varPi$ would contain more than one vertex. If there are only two stamens adjacent to $v_i$ (see Fig. 13c), then either there is a double edge in G, or $v_i$ belongs to the outer cycle of G. The latter can not be the case, since C is a strictly internal cycle of G, as ensured in the beginning of the proof. So $C^{\prime }_{{\mathrm {shell}}}$ contains three or more stamens $s_1,\ldots ,s_k$ of C, and they are all adjacent to $v_i$. Fig. 13b illustrates the construction of lines $\ell (s_1),\ldots , \ell (s_k)$ in this last case. Notice that the angles between two consecutive half-lines $\ell (s_1),\ldots ,\ell (s_k)$ can be made less than $\pi$, since $v_i$ is not flat. Thus we can again proceed as in the non-degenerate case. This concludes the proof of the claim.

Let $\varGamma ^{\prime }_{{\mathrm {shell}}}$ be the constructed drawing of $G^{\prime }_{{\mathrm {shell}}}$. Recall that each petal or stamen w of C, that does not belong to $C^{\prime }_{{\mathrm {shell}}}$, lies in a face of $G^{\prime }_{{\mathrm {shell}}}$, denoted by ${\mathrm {shell}}(w)$. Let $\varGamma _{{\mathrm {shell}}(w)}$ denote the polygon representing face ${\mathrm {shell}}(w)$ in $\varGamma ^{\prime }_{{\mathrm {shell}}}$. By construction, ${\mathrm {cone}}(w) \cap \varGamma _{{\mathrm {shell}}(w)} \ne \emptyset$. We next explain how to extend the drawing of $G^{\prime }_{{\mathrm {shell}}}$ to the drawing of $G_{{\mathrm {shell}}}$. For each edge (u, v) of $C^{\prime }_{{\mathrm {shell}}}$, we add a convex curve, lying close enough to this edge inside $\varGamma ^{\prime }_{{\mathrm {shell}}}$. More precisely, we consider the perpendicular bisector of the edge (u, v) and place a point o on this line, so that o is closer to (u, v) than any apex point inside $\varGamma _{{\mathrm {shell}}(w)}$. We then construct a parabola with origin o passing through the vertices u and v. Let $\mu$ be the closed curve that is formed by the union of the parts of all these parabolas (one for each edge of $C^{\prime }_{{\mathrm {shell}}}$) that lie inside $C^{\prime }_{{\mathrm {shell}}}$. We notice that we have placed them so that all the points of $\{{\mathrm {apex}}(w) \mid w\in C\}$ are still in the interior of $\mu$. Thus $\mu$ is intersected by all the sets ${\mathrm {cone}}(w)$, for each $w \in C$. We place each vertex w of $C_{{\mathrm {shell}}} \setminus C^{\prime }_{{\mathrm {shell}}}$ on $\mu \cap {\mathrm {cone}}(w)$ in the order they appear in $C_{{\mathrm {shell}}}$. Since all edges induced by $C_{{\mathrm {shell}}}$ lie outside of $C_{{\mathrm {shell}}}$, and both endpoints of such an edge are placed on a single convex curve, they can be drawn straight without intersecting each other, or other edges of $G_{{\mathrm {shell}}}$. Thus, we have constructed a planar extension of $\varGamma _C$ to a drawing of $G_{{\mathrm {shell}}}$, call it $\varGamma _{{\mathrm {shell}}}$.

Recall the definitions of faces of C, faces of $C_{{\mathrm {shell}}}$ and petal faces from the beginning of this section. The faces of C appear in $\varGamma _{{\mathrm {shell}}}$ as convex polygons. The faces of $C_{{\mathrm {shell}}}$ are triangles, and the petal faces of $G_{{\mathrm {shell}}}$ are star-shapes whose kernel is close to the corresponding petal. By Observation 1, each vertex of $G \setminus G_{{\mathrm {shell}}}$ either lies in a face of C, or in a face that is a triangle, or in a petal face, or outside $C^{\prime }_{{\mathrm {shell}}}$. Moreover, a subgraph of G inside a petal face is triconnected. Thus, by multiple applications of Theorem 1, we can extend the drawing of $G_{{\mathrm {shell}}}$ to a straight-line planar drawing of the subgraph of G inside $C^{\prime }_{{\mathrm {shell}}}$.

Finally, notice that in the constructed drawing of $G_{{\mathrm {shell}}}$ each petal of its outer cycle, i.e., $C^{\prime }_{{\mathrm {shell}}}$, is realizable (Claim 2). Moreover, by construction of $G_{{\mathrm {shell}}}$, $C^{\prime }_{{\mathrm {shell}}}$ has no outer chords. Thus, we can apply Theorem 3, to complete the drawing of G lying outside $C^{\prime }_{{\mathrm {shell}}}$.

The time complexity of the construction is determined by the following basic operations: an application of Proposition 1; the construction of a constant number of subgraphs of linear size, namely $C_{{\mathrm {shell}}}$, $G_{{\mathrm {shell}}}$, $C^{\prime }_{{\mathrm {shell}}}$ and $G_{{\mathrm {shell}}}^{\prime }$; a constant number of traversals of these subgraphs, for computing cones, apex points, polygon $\varPi ^{\prime }$ and the actual drawing of these subgraphs; a linear number line-line intersections to construct the apex points and the cones; the construction of a linear number of lines to host the vertices of $C^{\prime }_{{\mathrm {shell}}}$; a traversal of the neighborhood of $C^{\prime }_{{\mathrm {shell}}}$ to determine which edge to “stretch” for the one-sided representation of $C^{\prime }_{{\mathrm {shell}}}$; a linear number of parabola-line intersections for the placement of vertices of $C^{\prime }_{{\mathrm {shell}}}$; the construction of a number of parabolas to form the curve $\mu$, which takes time proportional to the number of apex points plus the size of $C^{\prime }_{{\mathrm {shell}}}$, which is linear in total; multiple applications of Theorem 1, each of which runs in time linear in the number of vertices it places; and finally, an application of Theorem 3. Thus, we conclude that the overall time complexity of the construction is O(n). $\square$

Fig. 11

Construction of Case 1. Corresponding $G_{{\mathrm {shell}}}$ is shown in Fig. 9b

Fig. 12

a–b Case 2: Polygon $\varPi$ is degenerated and has two vertices. c Case 3: Polygon $\varPi$ is degenerated and has a single vertex, and $C^{\prime }_{{\mathrm {shell}}}$ contains three or more stamens of C adjacent to the same vertex

Fig. 13

a Construction in Case 2.a. b Construction in Case 3. c If $C^{\prime }_{{\mathrm {shell}}}$ contains only two stamens of C, then a vertex of C, $v_i$, belongs to the outer cycle of G

We conclude with the following general statement that follows from Theorem 4 and one of the known algorithms that constructs drawing of a planar graph with a prescribed outer face (e.g. [5, 12] or Theorem 1).

Theorem 5

Let G be a plane graph and H be a biconnected plane subgraph of G. Let $\varGamma _H$ be a straight-line convex drawing of $\varGamma _H$. $\varGamma _H$ is extendable to a planar straight-line drawing of G if and only if the outer cycle of H is outerchordless and each petal of the outer cycle of H is realizable.

6 Conclusions

In this paper, we have studied the problem of extending a given convex drawing of a cycle of a plane graph G to a planar straight-line drawing of G. We characterized the cases when this is possible in terms of two simple necessary conditions, which we proved to also be sufficient.

It can be easily seen that the drawing area depends on the input. Thus, if C has a petal $w_{i,j}$, such that the edges $(v_i,v_{i+1})$, $(v_{j-1},v_j)$ of C (refer to Fig. 9a) are almost parallel, the area required for the drawing becomes arbitrarily large. Another situation which blows up the area is the following. Consider a cycle of length three which surrounds C and has one common vertex $v_i$ with C. If additionally $v_i$ is almost flat in C, i.e., edges $(v_{i-1},v_i)$ and $(v_i,v_{i+1})$ have almost the same slope, then the three-cycle needs to be arbitrarily long in order to contain C. Thus, our main open question is whether simple conditions forbidding such situations are sufficient to ensure that the area of the final drawing is polynomial. For our construction we have repeatedly used Theorem 1 [6], which also does not ensure that the area is polynomial. Thus, in order to answer our open question it also has to be investigated when a straight-line drawing inside a fixed star-shaped polygon has polynomial area.

Finally, as an extension of our research, it would be interesting to investigate whether more involved necessary conditions are sufficient for more general shapes of a cycle, for instance star-shaped polygons.