A planar graph is a graph that can be drawn on the plane in such a way that its edges intersect only at their endpoints. Such a drawing is called a planar embedding. A planar embedding divides the plane into a set of regions called faces. Face incident to vertices Ui, ..., um, where m ^ 3, we denote by (u1,..., um). The face with unbounded area is an outer face. Other faces are inner. An edge is outer if it belongs to the outer face, and it is inner otherwise.
An outerplanar graph is a graph that admits an outerplanar drawing,
e., a planar drawing in which all vertices are on the outer face. The weak dual G* of a planar graph G is the graph having a node for each inner face of G, and an edge between two nodes if and only if the two corresponding faces share an edge. For an outerplanar graph G, its weak dual G* is a tree. Outerpath is a outerplanar graph, whose weak dual graph G* is a path.
A directed graph G = (V, E), or a digraph, is a graph whose edges have an orientation. We assume each edge e = (u, v) of G to be oriented from u to v, and hence denote u and v as the tail and head of e, respectively. A vertex u of G is a source (resp. a sink) if it is the tail (resp. the head) of all its incident edges. A directed cycle is a cycle in directed graph in which each edge is traversed in the same direction. A directed acyclic graph (DAG) is a digraph that contains no directed cycle. An st-DAG is a DAG with a single source s and a single sink t.
An outerplanar graph is internally triangulated if it is biconnected and all inner faces are cycles of length 3. A fan is an internally triangulated outerpath whose inner edges all share an end-vertex. An st-outerplanar graph is an st-DAG whose underlying undirected graph is a outerplanar graph. An st-outerplanar graph is one-sided if the edge (s, t) is an outer edge. An st-fan is an st-DAG whose underlying undirected graph is a fan and whose inner edges have s as an endvertex. An st-outerpath is an s t-DAG whose underlying undirected graph is an outerpath.
A topological book embedding (TBE) of G is a planar drawing such that all vertices of G are represented as points of a horizontal line l, called the spine. All vertices of G are embedded on the spine in some order v1, v2,..., vn, hence we can use the notation vi < Vj, if i < j or we can say that Vi is lower than Vj. Each of the two half-planes defined by l is a page. Each edge in a TBE is either in the left page, or completely in the right page, or it can be on both pages, in which case it crosses the spine. We assume that in a topological book embedding every edge is drawn as a sequence of one or more circular arcs, in particular semi-circles, such that no two consecutive arcs are in the same page.
Notice that, by using semi-circles, two arcs in the same page cross each other only if their end-points alternate along the spine (fig. 4).
A monotone topological book embedding is a topological book embedding such that every edge crosses the spine at most once. An edge that crosses the spine once is called an S-edge and each of the two arcs composing it are called sub-edges. A non-S-edge (x, y) is called free, if there are no edges that cover the edge (x, y), i.e. there are no vertices u, v, such that u < x < y < v and edges (u, v) and (x, y) are on the same page (fig. 5). Let 7 be a monotone topological book embedding. TBE 7 is nice if there is no pair of S-edges whose sub-edges cover in the right page.
Hard case. Case where Fi is a triangle and F-1 is a right one-sided fan is difficult in that it is impossible to rotate the edge of e^-i: from right one-sided fan Fi-1 there could be an appendage H. Let H has vertices Vi,...,vn.
Step 1. Consider an appendage H with vertices si, u1,..., um, which is attached to the attachment edge (si, um). Vertex um is not yet embedded in TBE. Place it anywhere above vn. Since there is an invariant (I2), there are no edges under the edge e- on the same page. Therefore, the appendage H satisfies the condition of Lemma 4. Now we can embedd the H appendage. Since vn < ui, the H appendage is located strictly below the H appendage, so there is a gap between them. Strictly speaking, each appendage is located in its own funnel, and there is a distance between the funnels.
Step 2. Take a point q in this gap. Delete the old edge ei-1 and redraw it as an S-edge that intersects the spine at the point q. It remains only to embedd the edges (si, um) and (um, ti). Vertices Si, um, ti are already in TBE. Also, the S-edge has a point of intersection below the vertex um. Therefore, these edges can be drawn on the same page where the ei-1 edge used to be (fig. 30). Then the edge ei is also free, similar to the case where Fi -1 is a triangle or a two-sided fan (I1). And also the vertices um and ti are consecutive. Then this case satisfies the condition (I2).
In this case, an S-edge (Si, t-) is formed. Use the fact that Fj-i is a one-sided fan. When constructing Fi-1, no S-edge was formed. But it could have been formed during the construction of Fi-2. Then the S-edge of Fi-2 can have tail at Si = t- or lower. This means that the old S-edges do not intersect with the new S-edge.
