Constrained Level Planarity is FPT with Respect to the Vertex Cover Number
Boris Klemz Marie Diana Sieper


Tidal reconstruction of neutron star mergers from their late inspiral
    [
    
=====================================================================





The problem Level Planarity asks for a crossing-free
drawing of a graph in the plane such that vertices are placed at prescribed y-coordinates (called levels) and such that every edge is realized as a y-monotone curve.
In the variant Constrained Level Planarity,
each level y is equipped with a partial order ≺_y on its vertices and in the desired drawing the left-to-right order of vertices on level y has to be a linear extension of ≺_y.
Constrained Level Planarity is known to be a remarkably difficult problem:
previous results by Klemz and Rote [ACM Trans. Alg.'19] and by Brückner and Rutter [SODA'17] imply that it remains NP-hard even when restricted 
to graphs whose tree-depth and feedback vertex set number are bounded by a constant and even when the instances are additionally required to 
be either proper, meaning that each edge spans two consecutive levels, or ordered, meaning that all given partial orders are total orders.
In particular, these results rule out the existence of FPT-time (even XP-time) algorithms with respect to these and related graph parameters (unless P=NP).
However, the parameterized complexity of Constrained Level Planarity with respect to the vertex cover number of the input graph remained open.

In this paper, we show that Constrained Level Planarity can be solved in FPT-time when parameterized by the vertex cover number.
In view of the previous intractability statements, our result is best-possible in several regards:
a speed-up to polynomial time or a generalization to the aforementioned smaller graph parameters is not possible, even if restricting to proper or ordered instances.




§ INTRODUCTION



A large body of literature related to graph drawing is dedicated to so-called upward planar drawings, which provide a natural way of  visualizing a partial order on a set of items.
An upward planar drawing of a directed graph is a crossing-free drawing in the plane where every edge e=(u,v) is realized as a y-monotone curve 
that goes upwards from u to v, i.e., the y-coordinate strictly increases when traversing e from u towards v.
The most classical
computational
problem
in this context is Upward Planarity:
given a directed graph, decide whether it admits an upward planar drawing.
The standard version of this problem is NP-hard <cit.>,
but, if the y-coordinate of each vertex is prescribed, it can be solved in polynomial time <cit.>,
which suggests that a large part of the challenge 
of Upward Planarity
comes from choosing an appropriate y-coordinate for each vertex.
However, when both the y-coordinate and the x-coordinate of each vertex are prescribed, the problem is yet again NP-hard <cit.>,
indicating that another part of the challenge comes from drawing the edges in a y-monotone non-crossing fashion while respecting the given or chosen coordinates of their endpoints.
The paper at hand is concerned with the parameterized complexity of a generalization of the latter of these two variants of Upward Planarity, which is known as Constrained Level Planarity.
It is expressed in terms of so-called level graphs, which are defined next;
we adopt the notation and terminology used in <cit.>.



    Level Planarity.
 A level graph 𝒢=(G,γ) is a directed graph G=(V,E) together with a level assignment, 
which is a function[

Traditionally, in the literature, the level assignment γ is defined as a surjective function that maps to an integer interval { 1,2,… ,h};
it merely acts as a convenient way to encode a total preorder on V.
It is well known that the traditional and our (more general) definition are polynomial-time equivalent: 
algorithms designed assuming the classical definition can also be applied in the more general context: one simple has to first sort the vertices by y-coordinates and then apply the traditional algorithm using the sorting-ranks as y-coordinates.
We are using the given general definition as it eases the description of our algorithms; though, specific polynomial runtimes obtained in previous work that are stated in our introduction assume the classical definition.

] γ V→ℝ where γ (u)<γ (v) for every edge (u,v)∈ E.
For every i∈ℝ where V_i={ v∈ V|γ (v)=i} is non-empty, the set V_i is called a (the i-th) level of 𝒢.
The width of level V_i is |V_i|.
The level-width of 𝒢 is the maximum width of any level in 𝒢 and the height of 𝒢 is the number of (non-empty) levels.
A level planar drawing of 𝒢 is an upward planar drawing of G where the y-coordinate of each vertex v is γ (v). 
We use L_i to denote the horizontal line with y-coordinate i.
The level graph 𝒢 is called proper if every edge spans two consecutive levels, that is, for every edge (u,v)∈ E there is no level V_j with γ(u)<j<γ(v).
The problem Level Planarity asks whether a given level graph admits a level planar drawing.
In a series of papers <cit.>,
it was shown that Level Planarity can be solved in linear<ref> time;
we refer to <cit.> for a more detailed discussion of the history of the corresponding algorithm and of alternative approaches to solve Level Planarity.



    Constrained Level Planarity.

In 2017, Brückner and Rutter <cit.> and Klemz and Rote <cit.> independently 
introduced and studied two closely related variants of Level Planarity,
which are defined in the following.

A constrained level graph 𝒢=(G,γ,(≺_i)_i) is a triple 
corresponding to a level graph (G, γ)  equipped with a family (≺_i)_i containing, for each level V_i, a partial order ≺_i on the 
vertices V_i.
A constrained level planar drawing of 𝒢 is a level planar drawing of (G, γ) where, for each level V_i, the left-to-right 
order of the vertices V_i corresponds to a linear extension of ≺_i.
For a pair of vertices u,v∈ V_i with u≺_i v, we refer to u≺_i v as a constraint on u and v.
The problem () asks whether a given constrained level graph admits a constrained level planar drawing.

() corresponds to the special case of where the given partial orders are total orders, 
which is polynomial time equivalent to prescribing the x-coordinate (in addition to the y-coordinate) of each vertex.

Klemz and Rote <cit.> established a complexity dichotomy for with respect to both the maximum degree and the level-width.
In particular, they showed that is NP-hard even when restricted to the case where 𝒢 has a level-width 
of 2 and the underlying undirected graph of G is a disjoint union of paths, i.e., a graph of maximum degree 2, path-width (and tree-width) 
1, and feedback vertex/edge set number 0.
In fact, with a simple modification[
In the variable gadget of every variable u_j, one can remove the subdivision vertices of the tunnels with index larger than j.
This modification does not influence the realizability of the instance since the left-to-right order of all tunnels is already fixed due to the subdivision vertices on level ℓ_0.
] to their construction, the underlying undirected graph produced by the reduction becomes a disjoint union of paths with constant length, implying that even the tree-depth is bounded.
(The definitions of all these classical graph parameters can be found, e.g., in <cit.>.)

It follows that is NP-hard in the same scenario and when, additionally, each of the prescribed partial orders ≺_i is a total order.

is (trivially) solvable in linear<ref> time when restricted to proper instances <cit.>.
In contrast, an instance of can always be turned into an equivalent proper instance by subdividing each 
edge on each level it passes through without introducing any constraints on the resulting subdivision vertices <cit.>.
Hence, is NP-hard even in the proper case.

Independently, Brückner and Rutter <cit.> also presented a proof for the NP-hardness of , which relies on a very different strategy.
It is not obvious whether the graphs produced by their construction have bounded tree-width, 
however, it is not difficult to see[
In the strongly NP-hard 3-Partition problem <cit.>, one has to partition 3n positive integers 
B/4<a_1,a_2,…,a_3n<B/2 of total sum nB into n triples (or buckets) of sum (or size) B.
To reduce to , one can simulate a bucket of size B as a sequence of B consecutive sockets and a 
number a_i as a_i plugs that are connected in a star-like fashion to a common ancestor v_i located above all these plugs.
Finally, all ancestors v_i and all sockets are connected in a star-like fashion to a common root vertex.
] that the socket/plug gadget used in their reduction can be utilized in the context of a reduction from 3-Partition to show that 
remains NP-hard for proper instances whose underlying undirected graph is a single (rooted) tree of constant depth.
In fact, the unpublished full version of <cit.> features such a construction <cit.>.

On the positive side, Brückner and Rutter <cit.> presented a polynomial time algorithm for the special case of 
where the input graph G has a single source.
They further improved the runtime of this algorithm in <cit.>.
Very recently, Blažej, Klemz, Klesen, Sieper, Wolff, and Zink studied the parameterized complexity of and with respect to the height of the input graph <cit.>.
They showed that parameterized by height is XNLP-complete (implying that it is in XP, but W[t]-hard for every t≥ 1).
In contrast, is NP-hard even if restricted to instances of height 4, but it can be solved in polynomial time if restricted to instances of height at most 3.



    Other related work.

Several other
restricted
variants of Level Planarity have been studied, e.g., 
Clustered Level Planarity <cit.>, 
T-Level Planarity <cit.>, 
and Partial Level Planarity <cit.>.
In particular, in Partial Level Planarity,
 a given level planar drawing of a subgraph of the input graph 𝒢 has to be extended to a
full 
drawing of 𝒢, 
which can be seen as a generalization of and, in the proper case, a specialization of .

  Level Planarity has been extended to surfaces different from the plane <cit.>.
There are also related problems with a more geometric flavor, e.g.,
finding a level planar straight-line drawing where each face is bounded by a convex polygon 
<cit.>,
and problems where the input is an undirected graph without a level assignment and the task is to find a crossing-free drawing with y-monotone edges that, if interpreted as a level planar drawing,
satisfies or optimizes certain criteria, e.g., being proper or having minimum height <cit.>.



    Contribution.

As discussed above, the previous results of Brückner and Rutter <cit.> and Klemz and Rote <cit.> 
rule out the existence of FPT-time (even XP-time) algorithms for when considering the tree-width, path-width, tree-depth, or feedback vertex 
set number as a parameter, even when restricted to OLP or proper CLP instances (unless P=NP).
As all of these parameters are bounded[More precisely, tw(G)≤pw(G)≤td(G)-1≤vc(G) and fvs(G)≤vc(G).] by the vertex cover number, 
it is natural to study the parameterized complexity of with respect to this parameter.
We prove the following main result:



parameterized by the vertex cover number is FPT.


In view of the previous intractability statements, <ref> is best-possible in several regards:
a speed-up to polynomial time or a generalization to the aforementioned smaller graph parameters is not possible, even if restricting to OLP or proper CLP instances.



    Organization.

The proof of <ref> and the remainder of this paper are organized as follows.
We begin by introducing some basic notation, terminology, and other preliminaries in <ref>.
In particular, we describe a partition of the vertex set of a given constrained level graph 𝒢 into different categories with respect 
to a given vertex cover C and we show that the vertices of two of these categories are, in some sense, easy to handle.
In <ref>, we introduce cores and (refined) visibility extensions of level planar drawings with respect to a fixed vertex cover C.
Intuitively, the core-induced subdrawing of a (refined) visibility extension of a constrained level planar drawing Γ^* of 𝒢 with respect 
to C is a drawing Λ_core that captures crucial structural properties of Γ^* and whose total complexity is bounded in |C|.
The latter allows us to efficiently obtain such a core-induced subdrawing via the process of exhaustive enumeration.
This is the first main step of the algorithm corresponding to the proof of <ref>, which is described in <ref>.
Due to the properties of the core-induced subdrawing, it is then possible to place the remaining vertices 
in the subsequent main steps of the algorithm, each of which is 
concerned with the placement of the vertices of a particular vertex category.
We conclude with a discussion of an open problem in <ref>.
Proofs of statements marked with a (clickable) ⋆ can be found in the appendix.



§ PRELIMINARIES





    Conventions.

Recall that in a level graph 𝒢=(G=(V,E),γ), the graph G is directed by definition.
However, when it comes to vertex-adjacencies, we always refer to the underlying undirected graph of G, that is, the neighborhood of v∈ V is N_G(v)={u∈ V| (u,v)∈ E ∨ (v,u)∈ E}, the degree of v is |N_G(v)|, and “a vertex cover of G” refers to a vertex cover[A vertex cover of an undirected graph G=(V,E) is a vertex set C⊆ V such that every edge in E is incident to at least one vertex in C. The vertex cover number of G is the size of a smallest vertex cover of G.] of the underlying undirected graph of G.

The level planar embedding of a level planar drawing of 𝒢  lists, for each level V_i, the left-to-right sequence of vertices and edges intersected by the line L_i in the drawing.
Note that this corresponds to an equivalence class of drawings from which an actual drawing is easily derived, which is why algorithms for constructing level planar drawings (including our algorithms) usually just determine a level planar embedding.
For brevity, we often use the term “drawing” as a synonym for “embedding of a drawing”.



    Vertex categories & notation.

For m∈ℕ, we use [m] to denote the set {1,2,…,m}.
Let 𝒢=(G=(V,E),γ) be a (constrained) level graph and let C be a vertex cover of G.
An ear of 𝒢 with respect to C is a degree-2 vertex of V∖ C that is a source or sink.
For a subset X ⊆ C, we define V_X(C) = {v ∈ V∖ C |N_G(v) = X}.
We partition the vertices V∖ C of the graph G into four sets V_=0(C), V_=1(C), V_=2(C), V_≥ 3(C) where
V_=0(C) = { v ∈ V∖ C |deg(v) = 0},
V_=1(C) = { v ∈ V∖ C |deg(v) = 1} (the leaves),
V_=2(C) = { v ∈ V∖ C |deg(v) = 2}, and
V_≥ 3(C) = { v ∈ V∖ C |deg(v) ≥ 3}.
The set V_=2(C) is further partitioned into two sets V_=2^e(C), V_=2^t(C) where V_=2^e(C) contains the 
ears and V_=2^t(C) the non-ears, called transition vertices.
Let v∈ V_=1(C) and let c∈ C denote its (unique) neighbor.
We say that v is a leaf of c.
Similarly, let u∈ V_=2(C) and let c_a,c_b∈ C denote its (unique) two neighbors.
We say that u is a transition vertex (ear) of c_a and c_b if u∈ V_=2^t(C) (if u∈ V_=2^e(C)).
We often omit C if it is clear from the context.

Let 𝒢=(G=(V,E),γ,(≺_i)_i) be a constrained level graph and let C be a vertex cover of G.
The main challenge when constructing a constrained level planar drawing of 𝒢 is the placement of the leaves, ears, and transition vertices (along with their incident edges).
Indeed, it is not difficult to insert the isolated vertices (which include V_=0) in a post-processing step (performing a topological sort on each level), see <ref>.
Moreover, since we may assume G to be planar, the size of V_≥ 3(C) is linear in |C|.
This well known bound can be derived, e.g., by combining the fact that the complement of a vertex cover is an independent set with the following statement (setting A=C).


Let G=(V,E) be a planar graph and A⊆ V.
Then there are at most 2|A| connected components in the subgraph of G induced by V∖ A that are adjacent to more than two vertices of A.



Let G be a planar graph and let C be a vertex cover of G. Then |V_≥ 3(C)|≤ 2k, where k=|C|.

[lem:isolated]lemmaIsolated


 Let 𝒢 = (G, γ, (≺_i)_i) be a constrained level graph, let G' be the subgraph of G induced by the non-isolated vertices V',
and let γ' and (≺'_i)_i be the restrictions of γ and (≺_i)_i to V', respectively.
There is an algorithm that, given 𝒢 and a constrained level planar drawing Γ' of 𝒢'=(G',γ',(≺'_i)_i), constructs a constrained level-planar drawing of 𝒢 in polynomial time.



Our main algorithm will exploit the fact that only few ears may share a common level:

[cl:2k-ears-per-level]lemmaTwoK

	
	Let 𝒢=(G,γ) be a level graph, let Γ be a level planar drawing of 𝒢, let C be a vertex cover of G.
	Then there are at most 2|C| ears with respect to C per level. 





    Compatible edge orderings.

Let Γ be a level planar drawing of a (possibly constrained) level graph 𝒢=(G=(V,E),γ) without isolated vertices.
We will now define a useful (not necessarily unique) linear order ≺^e on the edges E with respect to Γ.
We refer to ≺^e as an edge ordering of E that is compatible with Γ.
Compatible edge orderings can be seen as a generalization of a linear order described in <cit.> for a 
set of pairwise disjoint y-monotone paths, which in turn follows considerations about horizontal separability of y-monotone sets by 
translations <cit.>.

Intuitively, ≺^e is a linear extension of a partial order in which e∈ E precedes f∈ E if it is possible to shoot a horizontal rightwards ray from e to f in Γ without crossing other edges before reaching f.
Formally, 

we say that a vertex v is visible from the left in Γ if the horizontal ray r_v emanating from v to the left intersects Γ only in v.
We say that an edge e=(u,v) is visible from the left in Γ if 
the closed (unbounded) region that is to the left of e and whose boundary is described by e, r_u, r_v intersects Γ only in e.
The order ≺^e is now constructed as follows:
the minimum of ≺^e is an edge e_1 of E that is visible from the left in Γ.
Such an edge always exists <cit.>:
among the edges whose lower endpoint is visible from the left, the edge with the topmost lower endpoint is visible from the left.
Let Γ' denote the drawing derived from Γ by removing e_1 and any isolated vertices created by the removal of e_1.
The restriction of ≺^e to the remaining edges E∖ e_1 corresponds to an edge ordering compatible with Γ', which is constructed recursively.
Note that 𝒢 and ≺^e uniquely describe
the drawing Γ and,
given 𝒢 and ≺^e, it is possible to construct Γ in polynomial time (by traversing ≺^e in reverse).



§ VISIBILITY EXTENSIONS AND CORES



In this section, 
we introduce and study 
(refined) visibility extensions and cores of level planar drawings.
We will see that the core-induced subdrawing of a (refined) visibility extension of a level planar drawing Γ with respect to some 
vertex cover C captures crucial structural properties of Γ while having a size that is bounded in |C|. 



    Visibility extensions.

Let Γ be a level planar drawing of a level graph 𝒢=(G=(V,E),γ).
A visibility edge e for Γ is
(1) a y-monotone curve that joins two vertices of Γ and can be inserted into Γ without creating any crossings (but possibly a pair of parallel edges);
or (2) a horizontal segment that joins two consecutive vertices on a common level of Γ and can be inserted into Γ without creating any crossings.
A visibility extension of Γ with respect to a vertex set V'⊆ V
is a drawing Λ derived from Γ by inserting a maximal set of 
pairwise non-crossing visibility edges incident only to vertices of V' such that for each pair e,e' of parallel edges in Λ there is at least one 
vertex of V' in the interior of the simple closed curve formed by e and e'; for an illustration see <ref>(a).
We remark that if V'=V, then Λ is essentially an interior triangulation containing Γ. However, we will always choose V' to be a (small) vertex cover, resulting in a much sparser yet still connected augmentation:

[lem:VC-connected]lemmaCconnected

Let 𝒢=(G=(V,E),γ) be a level graph without isolated vertices, let C be a vertex cover of G, let Γ be a level 
planar drawing of 𝒢,  let Λ be a visibility extension of Γ with respect to C, and let Λ_C be the subdrawing 
of Λ that is induced by C.
Then Λ_C is connected and has 𝒪(k) edges, where k=|C|.






    Cores and refined visibility extensions.

Intuitively, the core of a level planar drawing is a subset of the vertex set with certain crucial properties.
To define it formally, we will first classify the ears of the drawing according to several categories.
The concepts introduced in this paragraph are illustrated in <ref>(b).
Let 𝒢=(G=(V,E),γ) be a level graph, let C be a vertex cover of G, and let Γ be a level 
planar drawing of 𝒢.
Consider an ear v∈ V_=2^e(C)  with neighbors c_a,c_b where γ(c_a)≥γ(c_b).
If γ(v)>γ(c_a), we say that v is a top ear.
Otherwise (if γ(v)<γ(c_b)), we say that v is a bottom ear.
Assume that γ(c_a)> γ(c_b) and that v is a top ear.
If in Γ the edge c_bv is drawn to the left (right) of c_a, we say that v is a left (right) ear in Γ.
The terms “left” and “right” are defined analogously for bottom ears.
If γ(c_a)=γ(c_b), we consider v to be a left ear if it is a top ear; otherwise it is a right ear.

Consider a pair c_a,c_b∈ C with at least one left ear in Γ and let Γ' denote the subdrawing of Γ induced by the set of edges 
that are incident to at least one left ear of c_a,c_b in Γ.
Note that either all these ears are top ears or all these ears are bottom ears in Γ, and they are arranged in a nested fashion.
In case of top (bottom) ears, we refer to the unique one with the largest (smallest) y-coordinate as the outermost left ear of c_a,c_b.
The innermost left ear of c_a,c_b is defined symmetrically.
If Γ' has an interior (i.e., bounded) face f
such that the open region enclosed by the boundary of f contains a vertex of C in Γ,
then we say that the two 
ears v_1,v_2 on the boundary of f are bounding ears of c_a,c_b in Γ with respect to C.
Moreover, we say that v_1,v_2 are a pair of matching bounding ears whose region corresponds to f.
The terms “outermost”, “innermost” and “(region of matching pair of) bounding ears” are analogously defined for the right ears of c_a,c_b.
Every vertex of Γ that is an outermost, innermost, or bounding ear (with respect to some pair c_a,c_b∈ C) is called crucial with respect to C.

The core of Γ with respect to C is the (unique) subset of V that contains C, V_≥ 3(C), as well as all crucial ears of Γ with respect to C.
The subdrawing Λ_core of a visibility extension Λ of Γ with respect C that is induced by the core of Λ with respect to C captures crucial structural properties of Γ, which we will exploit in our main algorithm for constructing constrained level planar drawings in FPT-time.
Due to the fact that Λ_core has only 𝒪(|C|) vertices and edges, it is not difficult to “guess” Λ_core in XP-time (via the process of exhaustive enumeration) when given 𝒢 and C.
The main bottleneck is the enumeration of all possible sets of crucial ears.
To improve the runtime of this step to FPT-time,
we will now describe a variant of visibility extensions that contains some additional ears, which take over the role of the original crucial vertices. Loosely speaking, one can create such a drawing by placing one or two new ears near each crucial ear in a visibility extension. The resulting augmentation retains the helpful structural properties of its underlying visibility extension and we will see that the (positions of the) crucial vertices of some such augmentation can be guessed more efficiently since we can restrict the possible levels of these new vertices to a small set.
Formally, a refined visibilty extension Λ' of Γ is a crossing-free drawing of a level graph 𝒢'=(G'=(V', E'),γ') such that G is a subgraph of G', C is a vertex cover of G',
every vertex in V'∖ V is an ear with respect to C and its incident edges are drawn as y-monotone curves,
the subdrawing of Λ' induced by V is a visibility extension Λ of Γ, 
the crucial ears of Λ' are precisely the vertices in V'∖ V,
and |V'∖ V| ∈𝒪(|C|).



[lem:size-of-core]lemmaSizeCore

Let 𝒢=(G=(V,E),γ) be a level graph without isolated vertices, let C be a vertex cover of G, let Γ be a level 
planar drawing of 𝒢, let Λ be a refined or non-refined visibility extension of Γ with respect to C, and let Λ_core the 
subdrawing of Λ induced by the core of Λ with respect to C.
Then Λ_core is connected and has 𝒪(k) vertices and 𝒪(k) edges, where k=|C|.






§ ALGORITHM



In this section, we describe the algorithm corresponding to the proof of <ref>.
Let 𝒢=(G=(V,E),γ,(≺_i)_i) be a constrained level graph and let C be a vertex cover of G.
Our goal is to construct a constrained level planar drawing of 𝒢 or correctly report that such a drawing does not exist.
In view of <ref>, we may assume that 𝒢 has no isolated vertices.
To construct the desired drawing, we proceed in three main steps.
In Step 1,

 we “guess” a core-induced subdrawing of a refined visibility extension of a constrained level planar drawing of 𝒢 with 
respect to C (via the process of exhaustive enumeration).
In Step 2,

  we augment our drawing by inserting the transition vertices of 𝒢 with respect to C.
In Step 3,

  we finalize our drawing by inserting the leaves and ears of 𝒢 with respect to C.





    Step 1: Guessing a core-induced subdrawing.

Assume that there is a constrained level planar drawing Γ^* of 𝒢, let Λ^* be a refined visibility extension of Γ^* with 
respect to C, and let Λ_core be the subdrawing of Λ^* induced by the core of Λ^* with respect to C.
The procedures corresponding to Steps 2 and 3 of our algorithm are guaranteed to produce a constrained level planar drawing (not necessarily Γ^*) 
of 𝒢 when given Λ_core.
Hence, the goal of Step 1 is to determine (or, rather, guess) Λ_core, given 𝒢 and C.
More precisely, we will construct a set ℱ of drawings such that Λ_core∈ℱ and the number 
|ℱ| of drawings in ℱ is sufficiently small.
For each drawing in ℱ, we then apply Steps 2 and 3 of the algorithm (incurring a factor of |ℱ| in the total running time).
Given that Λ_core∈ℱ, one of the iterations is guaranteed to terminate with a constrained level planar drawing of 𝒢.

[lem:step1]lemmaStepOne

Let 𝒢=(G=(V,E),γ,(≺_i)_i) be a constrained level graph without isolated vertices, let C be a vertex cover of G, and let Γ^* be a constrained level 
planar drawing of 𝒢.

There is an algorithm that, given 𝒢 and C, 
constructs a set ℱ of  
2^𝒪(klog k)
drawings in  
2^𝒪(klog k)· n^𝒪(1) 
time, where
n=|V| and k=|C|,

such that all drawings in ℱ have size 𝒪(k) and are level planar drawings of subgraphs of G induced by
C and V_≥ 3(C) 
that respect γ and the orderings ≺_i
and are augmented by some visibility edges and additional ears (with respect to C).
Further, there exists a refined visibility extension Λ^* of Γ^* such that the subdrawing Λ_core of Λ^* induced by the core of Λ^* with respect to C is contained in ℱ.





We introduce the following terminology:
let x be a vertex in a level planar drawing (possibly augmented by some horizontal edges).
Let ℓ be the y-coordinate of x and let ℓ' be the largest y-coordinate of a vertex below x (if there no such vertex, we set ℓ'=ℓ-1).
We say that the line L_(ℓ+ℓ')/2 is directly below x.
The line directly above x is defined symmetrically.

We proceed in two main steps.
In the first main step, we show that there exists a refined visibility extension Λ^* of Γ^*.
To this end, we start with a visibility extension Λ of Γ^* and describe an incremental strategy that performs a total of 𝒪(k) augmentation steps, in each of which a new ear is added that takes over the role of a crucial ear in Γ^*.
(The description of this first main step is deferred to the appendix.)
In the second main step, we discuss the construction of the desired family ℱ.
To this end, let Λ_core be the subdrawing of Λ^* induced by the core of Λ^* with respect to C.
The drawing Λ_core is uniquely described by 𝒢, C, the set of visibility edges of Λ_core (and Λ^*), the set of crucial ears of Λ_core (and Λ^*) together with their level assignments and their incident edges, and a compatible edge ordering of the nonhorizontal edges of Λ_core.
The graph 𝒢, as well as the vertex cover C are given, so it suffices to enumerate all possible options for the remaining elements.

There are m_vis∈𝒪(k) visibility edges by <ref>
and each of these visibility edges joins a pair of vertices in C.
Hence, there are at most k2^m_vis⊆ k^𝒪(k)⊆ 2^𝒪(klog k) possible options for choosing the set of visibility edges.
To enumerate the set of crucial ears along with their level assignments,
we mimic the aforementioned incremental strategy for constructing Λ^*:
we first enumerate all options to pick the pair of neighbors of the first new vertex along with its level,
then, for each of these options, we enumerate all options to pick the pair of neighbors of the the second vertex along with its level, etc.,
until we have obtained all options to pick the desired 𝒪(k) vertices together with their levels.
More precisely, suppose we have already enumerated all options to pick the first i vertices together with their neighbors and levels.
For each of these options, to enumerate all options to pick the next vertex v', we go through all ways to pick its two neighbors u,w∈ C and through all ways to pick the level of v'.
There are 𝒪(k) pairs of vertices in C with ears (by <ref>).
To bound the number of ways to pick the level of v', we make use of the fact that whenever the incremental strategy for constructing Λ^* places a new vertex v', it is assigned to a new level directly above or below a level of one of the following categories:


  * a level with a vertex in C (𝒪(k) possibilities),

  * a level with a vertex in V_≥ 3(C) (𝒪(k) possibilities by <ref>),

  * a level of a vertex that does not belong to 𝒢, i.e., a level used for
one of the already placed vertices (𝒪(i)⊆𝒪(k) possibilities),

  * a level with a top-most or bottom-most vertex of 𝒢 (𝒪(1) possibilities),

  * a level with a top-most top ear, a top-most bottom ear, a bottom-most top ear, or a bottom-most bottom ear of some pair of vertices in C (𝒪(k) possibilities by <ref>),

  * a level with a top-most or bottom-most vertex of a connected component that contains a vertex of C in the graph obtained by removing u and w from the current graph (𝒢 together with the visbility edges and the already added vertices) (𝒪(k) possibilities).

In total, for a fixed pair of neighbors u,w, there are thus 𝒪(k) options to pick a level for v'.
We immediately discard level assignments for which v' is no ear.
By multiplying with the number of ways to choose the neighbors, we obtain 𝒪(k^2) options to choose v' and its level.
Multiplying the number of options for all 𝒪(k) steps together, we obtain a total number of k^𝒪(k)⊆ 2^𝒪(klog k) ways to create the set of crucial ears along with their levels.
By multiplying with the number of ways to choose the visibility edges, we obtain a total of 2^𝒪(klog k) options to choose the graph that corresponds to Λ_core.
For each of these options we enumerate all k^𝒪(k)⊆ 2^𝒪(klog k) permutations of the set of non-horizontal edges and, interpreting the permutation as a compatible edge order, try to construct a level planar drawing for which this order is compatible (cf. <ref>).
If we succeed,
we check whether the drawing is conform with (≺_i)_i and can be augmented with the horizontal visibility edges. If so,
we include the drawing in the set ℱ of reported drawings.
The size of the thereby constructed set ℱ is bounded by 2^𝒪(klog k) and it is guaranteed to contain Λ_core by construction.






    Step 2: Inserting transition vertices.

We now describe how to insert the transition vertices into the core-induced subdrawing Λ_core of the (refined) visibility extension Λ^*.
Our plan is to first show that in Λ^*, every transition vertex is placed “very close  to” some visibility edge.
Intuitively, this means that the visibility edges of Λ_core act as placeholders near which the transition vertices have to be placed.
We will describe a procedure that does so while carefully taking into account the given partial orderings ≺_i and prove its correctness by means of an (somewhat technical) exchange argument.

To formalize the notion of “very close to”, 
let e be an edge of a level planar drawing joining two vertices a,b
such that there is a degree-2 vertex t with neighbors a,b and
γ'(b)<γ'(t)<γ'(a)
where γ' is the level assignment.
We say that t is drawn in the vicinity of e with respect to a vertex set V' if the simple closed curve formed by e and the two edges incident to t does not contain a vertex of V' in its interior.

[lem:insertTransition]lemmaStepTwo


Let 𝒢=(G=(V,E),γ,(≺_i)_i) be a constrained level graph without isolated vertices, let C be a vertex cover of G, let Γ^* be a constrained level 
planar drawing of 𝒢, let Λ^* be a refined or non-refined visibility extension of Γ^* with respect to C, and let Λ_core the subdrawing
of Λ^* induced by the core of Λ^* with respect to C.
There is an algorithm that, given 𝒢, C and Λ_core,
inserts all transition vertices V_=2^t(C) (and their incident edges) into vicinities (with respect to C) of visibility edges in Λ_core in polynomial time such that the resulting 
drawing Λ^t_core can be 
extended to a drawing whose restriction to G is a constrained level planar drawing of 𝒢.





    Step 3: Inserting leaves and ears.


In this step, we start with the output of Step 2 and finalize our drawing by placing all the vertices that are still missing.



Let 𝒢=(G=(V,E),γ,(≺_i)_i) be a constrained level graph without isolated vertices, let C be a vertex cover of G, let Γ^* be a constrained level 
planar drawing of 𝒢, let Λ^* be a refined or non-refined visibility extension of Γ^* with respect to C
in which each transition vertex is placed in the vicinity of some visibility edge with respect to C,
and let Λ_core (Λ^t_core) be the subdrawing of Λ^* induced by the core (and the transition vertices) of Λ^* with respect to C.
There is an algorithm that, given 𝒢, C, Λ_core and Λ^t_core, extends Λ_core to a drawing Γ whose restriction to G is a constrained level planar drawing of 𝒢 in 2^𝒪(k^2log k)n^𝒪(1) time, where n=|V|,k=|C|.



The only vertices of G that are missing in Λ^t_core are the leaves and the non-crucial ears with respect to C (in case Λ^* is a refined visibility extension, the non-crucial ears are exactly the ears of 𝒢).

Our plan to insert them into our drawing is as follows.
We begin by introducing more structure in Λ^t_core and Λ^* by adding some additional visibility edges and making some normalizing assumptions, which will simplify the description of the upcoming steps.
In particular, this step will ensure that for each missing ear, there are essentially only (up to) two possible placements, which will allow us to enumerate all possible ear placements (so-called ear orientations) on a given level in FPT-time.
We then describe a partition of the plane into so-called cells in a way that is very reminiscent of the well-known trapezoidal decomposition from the field of computational geometry,
cf. <cit.>.
We merge some cells into so-called channels, which correspond to connected y-monotone regions in which the missing leaves along with their incident edges will be drawn (a region is y-monotone if its intersection with every horizontal line is connected).
We then introduce (and describe an enumerative process that constructs in FPT-time) a so-called traversal sequence that is compatible with Λ^*, which is a sequence of sets of channels with several useful structural properties related to Λ^*.
In particular, this sequence, in some sense, sweeps the plane from left to right in a way where for each edge incident to a leaf in Λ^*,
at some point there is a channel that contains it.
Exploiting the properties of the traversal sequence, we then describe how to construct a so-called insertion sequence for the leaves on a given level with respect to a given placement of the ears of that level in polynomial time.
Such an insertion sequence does not necessarily exist for every placement of ears, but we are guaranteed to find one by enumerating all possible ear placements of the level.
This computation is performed independently for each level.
Finally, we show how to construct in polynomial time the desired drawing Γ when given an insertion sequence
along with its ear placement for each level.
Notably, the final step can be executed even if  some of the ear placements are different from the ones used in Λ^*.
Let us proceed to formalize these ideas.



    Augmenting and normalizing Λ_core, Λ^t_core, and Λ^*.

Let e = (u,v) be a visibility edge of Λ^* (and Λ^t_core) that has at least one transition vertex in its vicinity.
In both Λ^t_core and Λ^*, we add two copies of e; one directly to the left of the leftmost transition vertex and the other 
directly to the right of the rightmost transition vertex in the vicinity of e,
which is possible to do in a y-monotone fashion and without introducing any crossings;
see <ref>(a).
Note that the region enclosed by these two edges only contains transitions vertices of u and v, as well as leaves of u or v.
We repeat this operation for all visibility edges e.

The following steps are illustrated in <ref>(b).
Let f be a face of Λ^t_core  that is bounded by four vertices v_1, v_2, u_1, u_2 where v_1, v_2 ∈ C and u_1, u_2 ∈ V_{v_1, v_2} are either both left ears or both right ears. 
Without loss of generality, assume they are both left ears with
γ(v_1)≤γ(v_2)<γ(u_1)<γ(u_2).
We add copies of the edges (v_1,u_2) and (v_2,u_2) in f in both Λ^t_core and Λ^*,
which can be done without introducing crossings.
These edges partition f into three regions.
Note that in Λ^* these regions only contain leaves and non-crucial ears.
Without loss of generality, we will assume that each leaf in f is either placed in the region bounded by (v_1,u_2) and its copy or the region bounded by (v_2,u_2) and its copy
(note that a leaf v that is adjacent to v_1 cannot have a constraint
of the form w≺_i v, where w is a non-crucial ear in f;
the situation for leaves adjacent to v_2 is symmetric).
Thus, the remaining (central) third region only contains non-crucial ears
and is henceforth called an ear-face of Λ^t_core.
We repeat this modification for all faces such as f.

For the remainder of the proof, Λ^t_core and Λ^* are used to refer to the thusly augmented and normalized drawings.
We also add all the new edges to Λ_core and use Λ_core to refer to this augmentation.
Note that this implies that it now suffices to search for a drawing of 𝒢 in which every non-crucial ear is placed in an ear-face, whereas no leaf is placed in an ear-face.





    Decomposition into cells.

We will now describe a partition of the plane that essentially corresponds to a
trapezoidal decomposition (cf. <cit.>) of Λ_core;
for illustrations refer to <ref>(c):
for each vertex v in Λ_core, shoot a horizontal ray from v to the left until hitting an edge or vertex of Λ_core, then add the corresponding segment to Λ_core.
In case the ray does not intersect any part of Λ_core, add the ray itself to Λ_core.
Perform a symmetric augmentation by shooting a horizontal ray from v to the right.
The maximal connected regions of the resulting partition of the plane are henceforth called cells.
We consider the cells to be closed.
Note that each cell is y-monotone and bounded by up to two horizontal segments or rays and up to two y-monotone curves.
By <ref>, Λ_core has 𝒪(k) vertices and edges (note that the augmentation step copies each edge at most twice) and, hence, it has 𝒪(k) faces.
Consequently, the number of cells is also 𝒪(k) since the insertion of a single segment or ray can only increase the number of faces (or, rather, maximal connected regions) by one.



    Channels.

Let v ∈ C, let R be a set of cells that do not belong to ear-faces, and let r∈ R.
Further, assume that R contains a cell that is incident to v. 
The triple c=(v,r,R) is a channel from v to r
 if it is possible to draw a y-monotone curve in Λ^t_core in the interior of the union of R that intersects  each cell in R and does not cross any edge of Λ^t_core;
as illustrated in <ref>(c).

We say that c can be used by a leaf w ∈ V_{v} and that the edge e_w incident to w can be drawn in c if e_w can be drawn in Λ^t_core in the union of R without any crossings and there is no channel (v,r',R') with this property for which R'⊂ R.
Further, we say that c is used by w if it can be used by w
and the edge incident to w is drawn in the union of R in Λ^*.
We use U to denote the set of all channels and U_used⊆ U to denote the set of all channels that are used.
The connectivity of Λ^t_core (cf. <ref>) can be used to show:

[claim:channelnumber_bounded]claimChannelNumber

	
	|U_used|≤ |U| ∈𝒪(k^2).





    Traversal sequences.

Let 𝒰 =  (𝒰_1, 𝒰_2, …, 𝒰_m) be a sequence of sets of channels.
We say 𝒰 is a traversal sequence if the following properties are fulfilled (see <ref> for illustrations):

	
  * 
		Let i∈ [m] and let (v,r,R)∈𝒰_i and (v',r',R')∈𝒰_i
		with v≠ v'.
		Then the intersection of the line L_γ(v) with the interior of the union of R' is empty.
	
  * 
		Let c be a channel and let a ≤ b be two indices such that c ∈𝒰_a and c ∈𝒰_b. 
		Then for every a ≤ i ≤ b, c ∈𝒰_i. 

We say a channel u is active in 𝒰_i if it is contained in it, and otherwise it is inactive in it. 
We say a traversal sequence 𝒰=(𝒰_1, 𝒰_2, …, 𝒰_m) is compatible with Λ^* if the following conditions are satisfied (refer again to <ref> for illustrations): 

	
  *  For every channel c, there exists an i∈ [m] such that c ∈𝒰_i if and only if c is used.
	
  *   There exists a compatible edge ordering ≺^e for the restriction of Λ^* to its nonhorizontal edges (recall that some visibility edges are horizontal) such that: 
		
			
  * 
				Let e, e' be two edges that are incident to leaves and where e ≺^e e', let c be the channel used 
				by e, and let c' be the channel used by e'.
				Then there exist indices i, i' such that i ≤ i' and c ∈𝒰_i, c' ∈𝒰_i'.
			
  * 
			Let c_1,c_2∈ U_used such that for every edge e_1 using c_1 and for every edge e_2 using c_2 we have e_1 ≺^e e_2. Then there is no index i∈ [m] such that 𝒰_i contains both
				c_1 and c_2 (and every index for which c_1 is active is smaller than every index where c_2 is active).
			
  * 
				For every pair of used channels c_1, c_2 such that c_2 is being used by an edge e that succeeds all edges that use c_1 in ≺^e there exists
				 an index i such that c_2 ∈𝒰_i and c_1 ∉𝒰_i (and c_1 is active for some index smaller than i).
		




[cl:compat-traversal-exists]claimTraversalSequence


	There exists a traversal sequence 𝒰=(𝒰_1, 𝒰_2, …, 𝒰_m) that is compatible 
	with Λ^* and whose length is
	m ∈𝒪(k^2).
	Moreover,
	there is an algorithm that, given 𝒢, C and Λ^t_core, computes a set of 2^𝒪(k^2log k) traversal sequences that contains 𝒰 in 2^𝒪(k^2log k)n^𝒪(1) time.



[claim:channels-unique-in-each-set]claimChannelsUniqueInEachSet

	
	Let 𝒰=(𝒰_1, 𝒰_2, …, 𝒰_m) be a traversal sequence that is compatible 
	with Λ^*, let i∈ [m], and let v be a leaf.
	Then 𝒰_i contains at most channel that can be used by v.





    Ear orientations.

Let i∈ [h] and let V^e_i⊆ V_i be all non-crucial ears on the ith level.
Further, consider a mapping s V^e_i →{left, right}.
We say that s is an ear orientation of level i.
We say that s is valid if it is possible to insert the ears V^e_i (on the line L_i) along with their incident edges into Λ^t_core such that
the resulting drawing Λ is crossing-free,
no constraint is violated (i.e., if u≺_i v, then u is placed to the left of v),
and for every v∈ V^e_i, we have that v is a left ear if and only if s(v)=left.
We say that Λ is induced by s.
Note that  for any ear v∈ V^e_i there is at most one left ear-face and at most one right ear-face into which it can be inserted without introducing crossings.
Hence, a valid ear orientation uniquely describes the ear-face in which each ear is placed.
Further, note that no two ears of V^e_i can be placed in the same ear-face without introducing crossings.
In contrast, whenever an ear orientation assigns only one ear to a given ear-face, it is possible to place the ear without introducing crossings.
These properties make it easy to test whether a given ear orientation is valid and, if so, construct the (unique) induced drawing in polynomial time.
In view of <ref>, this means we can enumerate all valid ear orientations of a given level in 2^2kn^𝒪(1) time.



    Insertion sequences.

Let 𝒰=(𝒰_1, 𝒰_2, …, 𝒰_m) be a traversal sequence that is compatible 
	with Λ^*.
Further, let i∈ [h], let s be a valid ear orientation of level i, and let Λ be its induced drawing. 
Finally, let 𝒬 =(Q_1, Q_2, …, Q_q) be a sequence with Q_t = (v, j), v ∈ V_i ∩ V_=1, and 1 ≤ j ≤ m for all 1 ≤ t ≤ q.
We say 𝒬 is an insertion sequence for i, s, and  𝒰 if the following conditions are fulfilled (for an example, see <ref>):

	
  *  
		Let v ∈ V_i ∩ V_=1. Then there exists at most one index t such that v ∈ Q_t.
	
  *  
		Let Q_x  = (v_x, j_x)∈𝒬 and Q_y = (v_y, j_y) ∈𝒬 with x < y. Then j_x ≤ j_y.
	
  *  
		Let Q_x= (v, j) ∈𝒬. Then there exists a channel c ∈𝒰_j that can be used by v.
	
  *  
		Let Q_x= (v, j)∈𝒬. Then for every w ∈ V_i ∩ V_=1 with w ≺_i v, there exists an 
		index x' < x such that w ∈ Q_x'.
	
  *  
		Let Q_x= (v, j)∈𝒬 and let (v,r,R) ∈𝒰_j be the (unique, by <ref>) channel usable by v in 𝒰_j. Then for every 
		w ∈ V_i ∖ V_=1 that is not a transition vertex in r and where v ≺_i w, w is 
		to the right of r or on the right boundary of r.
		 Symmetrically, for every 
		w ∈ V_i ∖ V_=1 that is not a transition vertex in r and where w ≺_i v, w is
		to the left of r or on the left boundary of r.


Let 𝒬 = (Q_1, Q_2, …, Q_q) be an insertion sequence for i, s, and 𝒰.
We say a leaf v∈ V_i ∩ V_=1 is choosable with regard to 𝒬 if (i) there exists an index j, such that (Q_1, Q_2, …, Q_q, (v, j)) is an 
insertion sequence for i, s, and 𝒰 as well and (ii) there exists no pair v', j',  with v' ∈ V_i ∩ V_=1 and j' < j such that 
𝒬 = (Q_1, Q_2, …, Q_q, (v', j')) is an insertion sequence. 



[cl:insertion-sequence-exists]claimInsertionSequenceExists


Let 𝒰=(𝒰_1, 𝒰_2, …, 𝒰_m) be a traversal sequence that is compatible 
	with Λ^* and let ≺^e be a compatible edge ordering for the restriction of Λ^* to its nonhorizontal edges, for which Property <ref> is fulfilled for 𝒰.
Further, let i∈ [h] and let s be the valid ear orientation of level i that is used in Λ^*.

For every q ∈{0, 1, …, |V_i ∩ V_=1|}, there exists an insertion sequence 
𝒬_q = (Q_1, Q_2, …, Q_q) for i, s, and 𝒰
such that the following two properties are satisfied (for an example, see <ref>):

Interval property:
For every vertex v ∈ V_i ∩ V_=1
there exists at most one nonempty maximal interval [a, b] where 0≤ a≤ b≤ q such that v is choosable with regard to 𝒬_j if 
and only if a ≤ j ≤ b. If such an interval [a, b] exists, then b=q or v∈ Q_b+1.
Conversely, if v occurs in some entry of 𝒬_q, then the interval exists. 

Dominance property: Let ≺^l_i be the restriction of ≺^e to edges incident to leaves on level i. Further, let Q_ℓ = (v_ℓ, j_ℓ)∈𝒬_q, let v_ℓ'∈ V_i ∪ V_=1, and let e_ℓ (e_ℓ') be the edge incident to v_ℓ (v_ℓ'). Then, if e_ℓ≺^l_i e_ℓ' or v_ℓ  = v_ℓ', we have j_ℓ≤ j', where j' is the maximum index such that the channel c' used by v_ℓ' (in Λ^*) is in 𝒰_j'.

Moreover, 𝒬_k is a prefix of 𝒬_k+1 for  all 0 ≤ k ≤ |V_i ∩ V_=1|-1.
Finally, there is an algorithm that,
given 𝒢, C, Λ^t_core,  𝒰, i and s, 
computes 
𝒬_|V_i ∩ V_=1| in polynomial time.





    Computing the drawing.

When given a traversal sequence that is compatible with Λ^*,
we can utilize <ref> to obtain a valid ear orientation together with an insertion sequence for a given level by simply trying to apply the algorithm corresponding to <ref> for all valid ear orientations of that level.
We do so for each level and then use the gathered information to construct the desired drawing by means of the following claim.
We remark that when the algorithm corresponding to <ref> successfully terminates, it is guaranteed to return an insertion sequence for the given valid ear orientation.
It might output an insertion sequence even if the given valid ear orientation is not the one used in Λ^*.
However, this does not invalidate our strategy as the following claim does not require that the given ear orientations are the ones used in Λ^*.

[cl:generate-drawing-from-ear-orientation]claimGenerateDrawingFromEarOrientation


There is an algorithm that, given 𝒢, C, Λ_core, Λ^t_core, 
a traversal sequence 𝒰=(𝒰_1, 𝒰_2, …, 𝒰_m) that is compatible 
	with Λ^*,
 and, for each level i∈ [h], a valid ear orientation s^i, as well as an insertion sequence 𝒬^i =(Q^i_1, Q^i_2, …, Q^i_q^i)
for i, s^i, and 𝒰
such that q^i = |V_i ∩ V_=1| (that is, 𝒬^i contains all leaves of level i),
computes an extension of Λ_core whose restriction to G is a constrained level planar drawing 
of 𝒢 in polynomial time.





    Wrap-up.

In the beginning of (and throughout the) proof of <ref>,
we have already sketched how the individual pieces of the proof fit together.
We formally summarize our strategy in the proof of the following claim.

[cl:summaryStep3]claimSumStepThree


There is an algorithm that, given 𝒢, C, Λ_core and Λ^t_core, extends Λ_core to a drawing Γ whose restriction to G is a constrained level planar drawing of 𝒢 in 2^𝒪(k^2log k)n^𝒪(1) time.



This concludes the proof of <ref>.





    Summary.

In the beginning of <ref>, we have already sketched how <ref> can be combined to obtain 
<ref>.
We formally summarize:

[thm:main-result]theoremMain


There is an algorithm that, given a constrained level graph 𝒢=(G=(V,E),γ,(≺_i)_i) and a vertex cover C of G, either constructs 
a constrained level planar drawing of 𝒢 or correctly 
 reports that such a drawing does not exist in time 2^𝒪(k^2log k)· n^𝒪(1), where n=|V| and k=|C|.




Given that a smallest vertex cover can be obtained in FPT-time with respect to its size <cit.>, our main result (<ref>) follows from <ref>.



§ DISCUSSION



We have shown that is FPT when parameterized by the vertex cover number.
A speed-up to polynomial time or a generalization to the smaller graph parameters (in particular, tree-depth, path-width, tree-width, and feedback vertex set number) is not possible, even if restricting to OLP or proper CLP instances.

Recall from <ref> that in the Level Planarity variant (),
a given level planar drawing of a subgraph of the input graph 𝒢 has to be extended to a
full 
drawing of 𝒢, 
which can be seen as a generalization of and, in the proper case, a specialization of .
An instance of can always be turned into an equivalent proper instance (and, thus, a instance) by subdividing each 
edge on each level it passes through.
However, in general this operation will (dramatically) increase the vertex cover number of the instance.
Hence, our techniques cannot (directly) be applied.
It thus is an interesting problem to study the parameterized complexity of with respect to the vertex cover number.















§ MATERIAL OMITTED FROM <REF> (PRELIMINARIES)


*



For each level V_ℓ, the drawing Γ' induces a linear order <_ℓ' on V_ℓ' that extends ≺'_ℓ.
Consider the order <_ℓ=(<_ℓ'∪≺_ℓ).
We claim that <_ℓ is a partial order, implying that the desired drawing can be obtained by performing a topological sort on each level.

To prove the claim, assume towards a contradiction that <_ℓ contains a cycle δ of the form v_1 <_ℓ v_2 <_ℓ… <_ℓ v_i < v_1.
Without loss of generality, we may assume that <_ℓ contains no cycle involving fewer vertices.
Since <_ℓ' and ≺_ℓ are partial orders, the cycle δ contains at least one isolated vertex and at least one non-isolated vertex.
Without loss of generality, we may assume that v_1 is isolated and v_i is non-isolated.
Let j (<i) be the largest index such that v_1,v_2,…,v_j are all isolated.
Since ≺_ℓ' only involves non-isolated vertices, it follows that v_i ≺_ℓ v_1 ≺_ℓ v_2 ≺_ℓ…≺_ℓ v_j+1 and, further, 
that j+1<i since ≺_ℓ is a partial order.
However, this implies that v_j+1<_ℓ v_j+2 <_ℓ… <_ℓ v_i <_ℓ v_j+1 is a cycle in <_ℓ involving fewer vertices than δ; a contradiction.
So indeed, <_ℓ is a partial order, as claimed.


*



Let i∈ [h].
We will use a charging argument to show that V_i contains at most 2|C| ears.
To this end, let Γ' denote the subdrawing of Γ that contains only the ears in V_i, as well as all vertices in C.
Let v be a vertex in C that is closest to the line L_i.
By planarity, this vertex can be adjacent to at most two ears of V_i.
We charge these ears to v and then delete them, as well as v from Γ'.
We repeat this strategy until all vertices in C (and, thus, all ears in V_i) have been deleted.
Every ear is charged to exactly one vertex in C and every vertex in C is charged at most twice, which implies the claim.




§ MATERIAL OMITTED FROM <REF> (VISIBILITY EXTENSIONS AND CORES)


*



We begin by proving the connectivity of Λ_C.
Let Λ' denote the (level planar) subdrawing of Λ that is induced by the non-horizontal edges.
Let S=(e_1,e_2,…,e_m') be a sequence of edges corresponding to a compatible edge ordering of Λ'.
We will show inductively that for each 1≤ i≤ m' the vertices of the subset V_E_i⊆ C of vertices in C that are incident to at least one 
of the edges in E_i={e_1,e_2,…,e_i} belong to the same connected component of Λ_C,
which establishes the connectivity of Λ_C since V_E_m'=C.

Clearly the claim holds for i=1.
Now let 1≤ j<m' and assume that the claim holds for each i≤ j.
We will show that the claim also holds for i=j+1.
Clearly, this is the case when e_j+1 is incident to a vertex of V_E_i, so assume otherwise.
Let v be a vertex of e_j+1 that belongs to C.
Consider the horizontal ray r_v emanating from v to the left.
To prove the claim, it suffices to show that v belongs to the connected component of Λ_C that contains V_E_i.

If r_v intersects Λ' only in v, then Λ contains a visibility edge that joins v with a vertex of C incident to e_1 (by 
definition of S, e_1 is visible from the left in Λ).
In this case, the claim follows since this vertex belongs to V_E_i.

So assume that r_v intersects Λ' not only in v.
Let p denote the first point ≠ v of Λ' that is encountered when traversing r_v from v.
Since there are no isolated vertices, p is located on some edge e_t.
Moreover, by definition of S, e_j+1, and v, it follows that t<j+1.
The definition of p asserts that there is a visibility edge between v and a vertex of C incident to e_t.
The claim follows since this vertex belongs to V_E_i, which concludes the proof of the connectivity of Λ_C.

To bound the number of edges, assume that Λ_C contains at least three edges (otherwise, the statement holds).
The drawing Λ_C may contain parallel edges, however, the definition of Λ and the connectivity of Λ_C
assert that each 
face of Λ_core (except for possibly the outer face, which could be bounded by two parallel edges) has at least three edges on its boundary.
Consequently, Euler's polyhedron formula yields that Λ_core has at most 3k-6+1∈𝒪(k) edges (the +1 accounts for the special role of the outer face).


*



We will prove the statement for non-refined visbility extensions; the statement for refined visibility extensions then follows easily by definition.
Recall that the core of Γ with respect to C is the subset of V that contains C, V_≥ 3(C), as well as all crucial vertices of Γ with respect to C.



    Connectivity.

We begin by showing that Λ_core is connected.
By <ref>, the subdrawing Λ_C of Λ (and Λ_core) that is induced by C is connected.
Moreover, since C is a vertex cover, every vertex of V_≥ 3(C), as well as every crucial vertex is adjacent to some vertex of C.
Consequently, Λ_core is connected, as claimed.



    Counting crucial vertices.

Recall that the crucial vertices Γ with respect to C are the ears that are outermost, innermost, or bounding ears of some pair of vertices of C.
We will examine the counts of these different types of vertices individually.



    Counting outer/innermost ears.

We begin by bounding the number of vertices that are outermost left ears.
Let V_outer^left⊆ V_=2(C) be the set of all these ears.
Let C'⊂ C be the set of vertices that are adjacent to at least one ear in  V_outer^left.
We will now construct a graph drawing Π as follows:
the vertex set of Π is C' and its vertices are placed exactly as in Λ.
Let v∈ V_outer^left and let c_a,c_b∈ C' denote the neighbors of v.
We add an edge between c_a,c_b in Π and use the simple curve formed by v and its incident edges in Λ to draw it.
This process is repeated for every ear v∈ V_outer^left.
The resulting drawing Π has |C'|≤ k vertices and |V_outer^left| edges, which are in one-to-one correspondence 
with the ears in V_outer^left.
Moreover, the drawing is by construction planar and has no parallel edges.
Hence, Euler's polyhedron formula implies |V_outer^left|≤ 3k-6.

The outermost right and the innermost left/right ears can be bounded analogously, which yields 𝒪(k) outermost and innermost ears in total.



    Counting bounding ears.

To count the number of bounding ears, we will use a charging argument.
Consider a matching pair v_1,v_2 of bounding ears of c_a,c_b∈ C with region r (which, by definition, contains at least one vertex of C).
If there is no pair of matching bounding ears whose region is a proper subset of r, we charge the pair v_1,v_2 to an arbitrary vertex of C in the interior of r.
Otherwise, let r'⊂ r be an inclusion-maximal region contained in r that is the region of a pair v_1',v_2' of matching bounding ears.
The boundary of r' contains exactly four vertices: v_1' and v_2', as well as two vertices of C.
At least one of the latter two has to be contained in the interior of r since r'⊂ r, say c∈ C.
Note that c is distinct from both c_a and c_b, which belong to the boundary of r.
We charge the pair v_1,v_2 to c.
This charging procedure is repeated for all matching pairs of bounding ears.

The inclusion-maximality of the regions r' implies that each vertex of C gets charged at most once:
consider a vertex c and assume it is charged by a pair v_1,v_2 of bounding ears with region r.
Then c is located in the interior of r.
Suppose there is another pair v_1',v_2' of bounding ears with region r' that is charged to c.
Then c is also located in the interior of r'.
By planarity and the fact that c is interior to both r and r', the boundaries of r and r' are nested, leaving two cases:
r'⊂ r or r⊂ r'.
In the case r'⊂ r, we obtain a contradiction since v_1,v_2 would have been charged to a vertex c̃ that is located on the boundary 
of r' or on the boundary of some region r” with r'⊂ r”⊂ r, implying that c̃ is distinct from c, which is interior to r'.
The case r'⊂ r is symmetric.
So indeed, each vertex of C is charged at most once, as claimed.
Moreover, no vertex of the outer (i.e., unbounded) face of Γ can be charged.
Since there are at least two vertices of C on the outer face (assuming |E|≥ 3), we obtain that the number of pairs of matching bounding ears is at most k-2.
Consequently, the number of bounding ears is at most 2k-4∈𝒪(k).



    Wrap-up.

We have shown that the number of crucial vertices is 𝒪(k).
The number of vertices in C is k by definition and the number of vertices in V_≥ 3(C) is 𝒪(k) by <ref>.
This yields a total number of n'∈𝒪(k) vertices in the core of Γ with respect to C.

The 𝒪(k)-bound on the number of visibility edges follows from <ref>.
When removing all visibility edges from Λ_core, we end up with a drawing without parallel edges.
Hence, Euler's polyhedron formula implies that its number of edges, and therefore the number of edges in Λ_core, is bounded by 3n'-6∈𝒪(k).





§ OMITTED MATERIAL FROM <REF> (ALGORITHM)


*



We proceed in two steps.
In the first step, we show that there exists a refined visibility extension Λ^* of Γ^* such that the set of vertices in Λ^* that do not belong to 𝒢 only use a restricted (small) set of levels.
In the second step, we use the results from the first step to discuss how to construct the desired family ℱ.



    Existence of Λ^*.

Towards the first step, let Λ be a visibility extension of Γ^*.
We apply the following normalization:
let a,b be a pair of matching bounding ears and let c,d∈ C be the common neighbors of a,b.
Without loss of generality, assume that the level of b is lower than the one of a and that a,b are top ears.
If the intersection I of the region R of a,b with the closed upper half-plane bounded by L_γ(b) is empty or contains only leaves of a,b,
then we redraw all edges of leaves of c whose upper endpoint is in I such that they intersect L_γ(b) directly to the right of (c,a) and then closely follow (c,a) towards c such that none of them has a vertex in R∖ I to its left.
Similarly, we can now redraw (c,b) such that it also has no vertex in R∖ I to its left.
We apply a symmetric transformation to the leaves of d and the edge (d,b).
Finally, we insert a maximal set of visibility edges to ensure that the result is again a visibility extension of Γ^*.
We repeat this strategy until the precondition of the redrawing procedure is unfulfilled for every pair of matching bounding ears.
A given edge might be redrawn multiple times, however, this procedure is guaranteed to terminate since each edge either moves monotonically to the left or moves monotonically to the right.
Overloading our notation, from now on we use Λ to denote the final redrawing.

We will now describe an iterative process that augments Λ (by inserting new ears) to obtain the desired refined visbility extension Λ^*.
Each new vertex created in this process will be placed on a “private” new level (of width 1).
To facilitate the description of the extended level assignment, we introduce the following terminology:
let x be a vertex in a level planar drawing (possibly augmented by some horizontal edges).
Let ℓ be the y-coordinate of x and let ℓ' be the largest y-coordinate of a vertex below x (if there no such vertex, we set ℓ'=ℓ-1).
We say that the line L_(ℓ+ℓ')/2 is directly below x.
The line directly above x is defined symmetrically.

Suppose we have already performed some number (possibly zero) of augmentation steps and let Λ' denote the resulting augmentation of Λ.
We now discuss how to perform the next augmentation step.
Let v∈ V be an ear of 𝒢 that is crucial in Λ' and let u,w∈ C denote its neighbors (if such a vertex v does not exist, we are done and Λ' is the desired representation Λ^*).
We describe a procedure that creates up to two new ears to ensure that v is no crucial ear of the resulting augmentation of Λ'.
Without loss of generality, let v be a top left ear (the other cases are handled symmetrically).
We iteratively consider four cases, which are not mutually exclusive (up to two can occur at the same time).





    Case 1.
 v is an outermost ear.
Let ϕ be a y-monotone curve whose lower endpoint is v,
whose interior does not intersect Λ', and
whose upper endpoint is either (i) on the line directly above the top-most vertex of Λ' 
or (ii) a vertex x of Λ' so that ϕ is between two incoming edges of x.
(Such a curve does always exist: it can be constructed by traversing upwards from v in a greedy-like fashion.)

If the upper endpoint of ϕ is of type (i), we place a new ear v' of u,w at the upper endpoint of ϕ and draw its incident edges by first following ϕ to v and then either the edge (u,v) or (w,v); see <ref>(a). 

If the upper endpoint of ϕ is of type (ii), then it is a vertex x such that either x ∈ C, x ∈ V_≥ 3(C), or x is a top ear of Λ'. We distinguish two subcases.

	If x ∈ C, x ∈ V_≥ 3(C), or x is the lowest top ear of its two neighbors,
	we place a new ear v' of u,w on the intersection of ϕ with the line directly below x and draw its incident edges by first following ϕ to v and then either the edge (u,v) or (w,v); see <ref>(b).
	
	If x is not the lowest top ear of its two neighbors, which we denote by y and z, we place a new ear v' of u,w on the intersection of ϕ with the line L directly above the top-most ear of u,w and draw its incident edges by first following ϕ to v and then either the edge (u,v) or (w,v); see <ref>(c).
	Note that ϕ indeed always intersects L:
	all ears of u,w lie inside the region R bounded by the cycle (x,z,x',y) where x' is the lowest top ear of y,z. It follows that the top-most ear of u,w (and, thus, L) is below x since the latter is the topmost point of R.
	
	Overloading our notation, from now on (when considering Cases 2–4) we use Λ' to denote the resulting drawing in which v no longer satisfies the assumption of Case 1.
	



    Case 2.

	v is an innermost ear.
	
	If v is a lowest top ear of u,w, 
	we place a new vertex v' on the line directly below v and between the two edges incident to v and draw the two incident edges of v' by following the incident edges of v; see <ref>(d).
	
	Otherwise, there exists an innermost right ear v^* of u,w whose level is lower than the level of v (since v is an innermost left ear); for illustrations refer to <ref>(e).
	 Among the vertices that are located in the region bounded by the cycle (u, v^*, w,v) and that are not leafs of u or w, let t be a top-most vertex (if the region does not contain such a vertex, we set t = v^*).
	 Assume without loss of generality that the edge (u,v) is to the left of the edge (w,v).
	 We place a new vertex v' on the line directly above t and between the two edges incident to v and to the right of the rightmost edge that is incident to a leaf of u (if any) and to the left of the leftmost edge that is incident to a leaf of w (if any).
	 We connect v' to u and w by going to the left and right until reaching edges. These edges must either be incident to v or to a leaf of u or w. In both cases, we can follow these edges to connect v' to u and w.
	 
	 Overloading our notation, from now on (when considering Cases 3–4) we use Λ' to denote the resulting drawing in which v no longer satisfies the assumptions of Cases 1–2.
	 
	 We conclude this case with a small observation that will later help with the construction of the desired family ℱ:
	if t ≠  v^*, then t can neither be a leaf of u or w nor an ear of u and w.
	It follows that in the graph obtained by removing u and w from Λ' there is at least one vertex of C in the connected component of t.
	The number of connected components that contain a vertex of C is bounded by 𝒪(k).
	Hence, the number of levels with a top-most vertex of one of these components is also bounded by 𝒪(k).
	



    Case 3.

There is a vertex v^* such that v,v^* is a pair of matching bounding ears of u,w in Λ' and v^* has a lower level than v.
Assume without loss of generality that the edge (u,v) is to the left of the edge (w,v); for illustrations refer to <ref>(f).
Among the vertices that are located in the region bounded by the cycle (u, v^*, w,v) and that are not leaves of u or w, let t be a top-most vertex.
If the level of v^* is above the one of t, by our normalizing assumption, we know that v^* is not a vertex of Λ.
In this case re-define t = v^*.
We place a new vertex v' on the line directly above t and between the two edges incident to v and to the right of the rightmost edge that is incident to a leaf of u (if any) and to the left of the leftmost edge that is incident to a leaf of w (if any).
We connect v' to u and w by going to the left and right until reaching edges. These edges must either be incident to v or to a leaf of u or w. In both cases, we can follow these edges to connect v' to u and w.

Overloading our notation, from now on (when considering Case 4) we use Λ' to denote the resulting drawing in which v no longer satisfies the assumptions of Cases 1–3.
	



    Case 4.

There is a vertex v^* such that v,v^* is a pair of matching bounding ears of u,w in Λ' and v^* has a higher level than v.
Similiar to Case 1, let ϕ be a y-monotone curve whose lower endpoint is v,
whose interior does not intersect Λ', and
whose upper endpoint is a vertex x of Λ' so that ϕ is between two incoming edges of x.
(Such a curve does always exist: it can be constructed by traversing upwards from v in a greedy-like fashion.)

If x ∈ C or x ∈ V_≥ 3(C),
	we place a new ear v' of u,w on the intersection of ϕ with the line directly below x and draw its incident edges by first following ϕ to v and then either the edge (u,v) or (w,v); see <ref>(g).

If x=v^*, then among the vertices that are located in the region bounded by the cycle (u, v^*, w,v) and that are not leaves of u or w, let t be a top-most vertex.
We place a new ear v' of u,w on the intersection of ϕ with the line L directly above t and draw its incident edges by first following ϕ to v and then either the edge (u,v) or (w,v); see <ref>(h).
	Note that ϕ indeed always intersects L by our normalization procedure
	(this is true even if v^* does not belong to Λ by construction).

Finally, assume that x is a top ear, but at least one of its adjacent vertices is neither u nor w.
Let y,z be the neighbors of x.
We place a new ear v' of u,w on the intersection of ϕ with the line directly below x and draw its incident edges by first following ϕ to v and then either the edge (u,v) or (w,v); see <ref>(i).
	Note that x is a lowest top ear of y,z since ϕ is crossing-free.

This concludes the description of Case 4, after which v no longer satisfies the assumptions of Cases 1–4.

We repeat this augmentation step until no crucial vertices of Λ are still crucial in Λ' yielding the desired refined visibility representation Λ^*.
Note that,  by <ref>, the total number of augmentation steps is 𝒪(k).



    Construction of ℱ.

We are now ready to discuss the construction of the desired family ℱ.
Let Λ_core be the subdrawing of Λ^* induced by the core of Λ^* with respect to C.
The drawing Λ_core is uniquely described by 𝒢, C, the set of visibility edges of Λ_core (and Λ^*), the set of crucial ears of Λ_core (and Λ^*) together with their levels and their incident edges, and a compatible edge ordering of the nonhorizontal edges of Λ_core.
The graph 𝒢, as well as the vertex cover C are given, so it suffices to enumerate all possible options for the remaining elements.

There are m_vis∈𝒪(k) visibility edges by <ref>
and each of these visibility edges joins a pair of vertices in C.
Hence, there are at most k2^m_vis⊆ k^𝒪(k)⊆ 2^𝒪(klog k) possible options for choosing the set of visibility edges.

To enumerate the set of crucial ears along with their level assignment,
we mimic the above construction of Λ^*:
we first enumerate all options to pick the pair of neighbors of the first new vertex along with its level,
then, for each of these options, we enumerate all options to pick the pair of neighbors of the the second vertex along with its level, etc.,
until we have obtained all options to pick 𝒪(k) vertices together with their levels.
More precisely, suppose we have already enumerated all options to pick the first i vertices together with their neighbors and levels.
For each of these options, to enumerate all options to pick the next vertex v', we go through all ways to pick its two neighbors u,w∈ C and through all ways to pick the level of v'.
There are 𝒪(k) pairs of vertices in C with ears by <ref>.
To bound the number of ways to pick the level of v', recall that whenever the above procedure places a vertex v', it is assigned to a new level directly above or below a level of one of the following categories:


  * a level with a vertex in C (𝒪(k) possibilities),

  * a level with a vertex in V_≥ 3(C) (𝒪(k) possibilities by <ref>),

  * a level of a vertex that does not belong to 𝒢, i.e., a level used for
one of the already placed vertices (𝒪(i)⊆𝒪(k) possibilities),

  * a level with a top-most or bottom-most vertex of 𝒢 (𝒪(1) possibilities),

  * a level with a top-most top ear, a top-most bottom ear, a bottom-most top ear, or a bottom-most bottom ear of some pair of vertices in C (𝒪(k) possibilities by <ref>),

  * a level with a top-most or bottom-most vertex of a connected component that contains a vertex of C in the graph obtained by removing u and w from the current graph (𝒢 together with the visbility edges and the already added vertices) (𝒪(k) possibilities by the observation at the end of Case 2).

In total, for a fixed pair of neighbors u,w, there are thus 𝒪(k) options to pick a level for v'.
We immediately discard level assignments for which v' is no ear.
By multiplying with the number of ways to choose the neighbors, we obtain 𝒪(k^2) options to choose v' and its level.
Multiplying the number of options for all 𝒪(k) steps together, we obtain a total number of k^𝒪(k)⊆ 2^𝒪(klog k) ways to create the set of crucial ears along with their levels.
By multiplying with the number of ways to choose the visibility edges, we obtain a total of 2^𝒪(klog k) options to choose the graph that corresponds to Λ_core.
For each of these options we enumerate all k^𝒪(k)⊆ 2^𝒪(klog k) permutations of the set of non-horizontal edges and, interpreting the permutation as a compatible edge order, try to construct a level planar drawing for which this order is compatible (cf. <ref>).
If we succeed,
we check whether the drawing is conform with (≺_i)_i and can be augmented with the horizontal visibility edges. If so,
we include the drawing in the set ℱ of reported drawings.
The size of the thereby constructed set ℱ is bounded by 2^𝒪(klog k) and it is guaranteed to contain Λ_core by construction.



*







The terminology introduced in the following paragraphs is illustrated in <ref>(a).
Let c_a,c_b∈ C such that there exists at least one transition vertex adjacent to both c_a and c_b, and let e_1, e_2,…, e_j denote be the 
visibility edges joining c_a and c_b in the left-to-right order in 
which they appear in Λ^*.
These edges partition the open horizontal strip S bounded by the lines L_γ(c_a) and L_γ(c_b) into regions r_1,r_2,… r_j+1 where e_i,1≤ i≤ j 
is on the boundary of r_i and r_i+1.

Let H_1, H_2, …, H_ℓ be the connected components of the graph represented by Λ^* after deleting c_a, c_b.
Note that these can contain vertices on the boundary 
or exterior to S.
However, by planarity, if a component H_i contains a vertex in a region r_i',2≤ i'≤ j, then all of its vertices are located in r_i' in Λ^*.
Similarly, if a component H_i contains a vertex exterior to all of the regions r_2,r_3,…,r_j in Λ^*, then all of its vertices are located exterior 
to all of the regions r_2,r_3,…,r_j.
When H_i contains a vertex of C in r_i',1≤ i'≤ j+1
in Λ^*, then this vertex is drawn in r_i' in Λ_core as well; we say that H_i is fixed to r_i'.
Additionally, when H_i contains a vertex of C that is not located in the open strip S, then we consider H_i to be fixed to both r_1 
and r_j+1 (representing the fact that H_i lies outside of the regions r_2,r_3,…,r_j).
In particular, every component H_i that contains at least two vertices also contains a vertex of C and is, thus, fixed to some region r_i'.
Consequently, the only components that are not fixed are the transition vertices of c_a and c_b and the leaves of c_a or c_b (since G has no isolated vertices).

The maximality of the set of visibility edges used to construct Λ^* implies that for each transition vertex v of c_a,c_b, there exists an 
index i such that there is no fixed component interior to the region bounded by e_i and the two incident edges of v,
in other words, v is drawn in the vicinity of e_i with respect to C.



    Algorithm.

To obtain Λ^t_core from Λ_core we will draw every transition vertex of c_a, c_b in the 
vicinity of one of the visibility edges of c_a, c_b.
To this end, we now define several sets and relations, for illustrations refer to <ref>(b).
Let ℋ be the set that contains all non-fixed components (i.e. the transition vertices and leaves of c_a and/or c_b), as well 
as the components that are fixed to one of the regions r_2,r_3,…,r_j.
For each region for which ℋ contains multiple fixed components, we merge all of these components into a single fixed subgraph 
and use ℳ to denote the resulting set, which consists of one fixed subgraph for each of the regions r_2,r_3,…,r_j,
 as well as the transition vertices and leaves 
of c_a and/or c_b.

We define a relation R on ℳ as follows:
M_α R M_β (with M_α∈ℳ and M_β∈ℳ) if and only if (1) there exists a vertex v_α in M_α 
and a vertex v_β in M_β such that v_α≺_γ(v_α) v_β or
(2) M_α and M_β are fixed subgraphs with M_α fixed to r_a, M_β fixed to r_b and a < b or
(3)  there exists a M_γ∈ℳ such that M_α R M_γ and M_γ R M_β.

The relation R is by definition transitive, but it is not necessarily a partial order.
Nevertheless, we will now describe a strategy to derive a total ordering from R that will be useful for placing the transition vertices:
suppose R contains a cycle δ of the form 
M_1 R M_2 R … R M_i R M_1, i≥ 2 of pairwise distinct elements M_1, …, M_i ∈ℳ.
Assume towards a contradiction that one element of δ, say M_1, consists of precisely one transition vertex v of c_a, c_b.
In Γ^*, the incident edges of v partition S into a left and a right side.
An inductive argument shows that all components in the cycle δ are drawn entirely on the right side, including M_1; a contradiction.
Consequently, all elements of δ must be fixed subgraphs or leaves.
Without loss of generality we may assume that M_1 consists of at least two vertices (δ cannot consist exclusively of vertices lying on a 
common level y since ≺_y is a partial order).
This implies that M_1 is fixed, say, to r_z (2 ≤ z ≤ j).
Similarly as before, inductive arguments show that all elements of δ have to lie to the right of e_z and to the left of e_z+1, i.e., in r_z.
Therefore M_1 is the unique fixed component of ℳ in r_z (and also the unique fixed component in δ).
We contract δ into a single subgraph inheriting all relations imposed by R on M_1, …, M_i.
In this fashion, we successively eliminate all cycles and eventually obtain an ordering
on the resulting set ℳ', which admits a linear extension ≤_ℳ'.

Observe that ordering of ℳ' corresponding to ≤_ℳ' is of the form 

    S^1, F^2, S^2, F^3, S^3, …, F^j, S^j,

where F^i denotes the fixed subgraph of ℳ' in r_i and each S^w is a sequence of transition vertices and leaves of c_a and/or c_b.
We remove all elements from ℳ' that correspond to leaves and denote the resulting set by ℳ”.
Let ≤_ℳ” denote the total order on ℳ” that corresponds to the  restriction of ≤_ℳ' to ℳ”.
Observe that the ordering of ℳ” corresponding to ≤_ℳ” is of the form 

    t^1_1, t^1_2, …, t^1_i_1, F^2, t^2_1, t^2_2, …, t^2_i_2, F^3, …, F^j, t^j_1, t^j_2, …, t^j_i_j,

where t^w_1, t^w_2, …, t^w_i_w is the restriction of S^w to the transition vertices.
For each 2≤ w ≤ j we draw t^w_1, t^w_2, …, t^w_i_w in the vicinity of the visibility edge e_w in this order (which can obviously be done without introducing crossings), see <ref>(c).

To obtain the desired drawing Λ^t_core, 
we repeat this procedure for every pair c_a, c_b ∈ C.
Clearly, all these steps can be performed in polynomial time.

We remark that it might seem tempting to draw the transition vertices, as well as the leaves according to ≤_ℳ', instead of just drawing 
the transition vertices according to ≤_ℳ”. However, this will in general not produce a drawing with the desired properties as there might 
be leaves affected by constraints of components fixed to r_1 and/or r_j+1, which are not taken into account when computing 
≤_ℳ' and ≤_ℳ”, as illustrated in <ref>(c).



    Correctness.


Suppose we have already carried out the above procedure for a set C_2 ⊂C2 of vertex cover vertex pairs c_a, c_b and obtained a 
drawing Λ_core^C_2 that consists of Λ_core augmented by all transition vertices that belong to some pair in C_2.
Assume inductively that Λ_core^C_2 can be extended to a drawing, without loss of generality Λ^*, whose restriction 
to G is a constrained level planar drawing of 𝒢.
Consider a pair c_a, c_b in C2∖ C_2 with at least one transition vertex  and let Λ_core^C_2' denote 
the drawing derived from Λ_core^C_2 by inserting the transition vertices of  c_a, c_b according to the above procedure.
Our goal is to show that Λ_core^C_2' can be extended to a drawing whose restriction to G is a constrained level planar drawing of 𝒢.
To this end, we will construct a drawing Λ from Λ_core^C_2 whose restriction to G is a constrained level planar 
drawing of 𝒢 and whose restriction to the graph represented by Λ_core^C_2' is Λ_core^C_2'.

Let Φ denote the simple closed curve corresponding to the boundary of the outer face of the subdrawing of Λ^* induced by the visibility 
edges joining c_a and c_b and the edges that are incident to some transition vertex of c_a,c_b.
We use Φ^- to denote the closed interior of Φ and Φ^+ to denote the open exterior of Φ.
Note that all visibility edges joining c_a and c_b and all transition vertices of c_a,c_b are located in Φ^- in Λ^* and, hence, 
all visibility edges joining c_a and c_b in Λ_core^C_2 are also located in Φ^-.

To construct Λ from Λ_core^C_2, we augment Φ^+ such that it looks exactly as in Λ^*.
Additionally, we draw the fixed subgraphs F^2,F^3,… F^j exactly as in Λ^*.
Let Λ' denote the resulting drawing.
To construct Λ from Λ', it remains to describe the placement of the  leaves of c_a and c_b (which we call leftover leaves) that 
are located in Φ^- in Λ^*, but do not belong to any fixed subgraph F^i (note that the leaves in Φ^+  in Λ^* and the leaves in 
the fixed subgraphs F^i have already been drawn in Λ'), as well as the placement of all the transition vertices of c_a,c_b (which are all located 
in Φ^- in Λ^* and, thus, have not yet been drawn in Λ').
To this end, we draw those leftover leaves and transition vertices that occur in the sequence S^w, 2≤ w≤ j in the vicinity of the visibility edge e_w in the 
order given by S^w (which can be done without introducing crossings).

Since ≤_ℳ' ⊆ ≤_ℳ”, the restriction of Λ to the graph represented by Λ_core^C_2' 
corresponds to Λ_core^C_2', as desired.
Hence, it remains to argue that the restriction Λ_G of Λ to G is a constrained level planar drawing of 𝒢.
By construction, Λ_G is a level planar drawing of 𝒢, so assume that some constraint u≺_γ(u) v is violated in Λ_G, 
i.e., u is drawn to the right of v on L_γ(u) (instead of to the left, as required).
By definition of Λ^*, the restriction of Λ' to its non-visibility edges is a constrained level planar drawing of the corresponding subgraph of 𝒢.
Consequently, one of u or v is a vertex of Λ that does not belong to Λ', i.e., a leftover leave or transition vertex of c_a 
and/or c_b, which lies in Φ^- in Λ^*.
Assume without loss of generality that this vertex is v (the other case is symmetric).
The definition of ≤_ℳ' implies that u lies in Φ^+ and, by assumption, to the right of Φ^-, which contains v.
However, by definition of Λ', the vertex u also lies to the right of Φ^- in Λ^*.
Since the vertex v also lies in Φ^- in Λ^*, it follows that the constraint u≺_γ(u) v is also violated in Λ^*; 
a contradiction to the definition of Λ^*.
So indeed, Λ (and, thus, Λ_core^C_2') satisfies all desired properties, proving the correctness of the algorithm.


*



Assume there are two channels (v,r,R_1),(v,r,R_2) with R_1≠ R_2 and such that the unique cell in R_1 that contains v and the unique cells in R_2 that contains v are identical.
Then there exist two cells r_a,r_b∈ R_1∩ R_2 with r_a above r_b
such that it is possible to draw two y-monotone curves c^1,c^2 that do not cross each other and that do not intersects any edge or vertex of Λ^t_core and where the endpoints p^1_a,p^1_b and  p^2_a,p^2_b of c^1 and c^2, respectively, satisfy the following properties:


  * p^1_a belongs to the lower boundary of r_a and the upper boundary of some cell r_a^1∈ R_1∖ R_2;

  * p^2_a belongs to the lower boundary of r_a and the upper boundary of some cell r_a^2∈ R_2∖ R_1;

  * p^1_b belongs to the upper boundary of r_b and the lower boundary of some cell r_b^1∈ R_1∖ R_2;

  * p^2_b belongs to the upper boundary of r_b and the lower boundary of some cell r_b^2∈ R_2∖ R_1.

By construction, the simple closed curve formed by c^1 and c^2 and the line segments p^1_ap^2_a and p^1_bp^2_b intersects no vertex or edge of Λ^t_core, has v in its exterior, and contains at least one vertex v'≠ v of Λ^t_core in its interior.
However, the connectivity of Λ^t_core (cf. <ref>) implies that Λ^t_core contains a path from v to v'; a contradiction.

It follows that for every pair of channels (v,r,R_1),(v,r,R_2) with R_1≠ R_2, the unique cell in R_1 that contains v and the unique cell in R_2 that contains v are distinct.
Consequently, we obtain |U| ≤ |R|·∑_v ∈ Cα(v), where α(v) denotes the number of cells incident to v for each v∈ C.
Recall that each cell is y-monotone and bounded by up to two horizontal segments or rays and up to two y-monotone curves.
Now, let v∈ C, let α^|(v) denote the number of cells incident to v for which v is incident to at least one y-monotone curve of the cell boundary, and let α^-(v) denote the number of the remaining cells incident to v (where v is incident only to horizontal segments or rays of the cell boundary).
Observe that α^-(v)≤ 2.
Additionally, each cell r can contain at most 4 vertices of C that are incident to y-monotone curves along the boundary of r.
Putting it all together, we obtain

    |U| ≤ |R|·∑_v ∈ Cα(v) = |R|· (∑_v ∈ Cα^|(v) + ∑_v ∈ Cα^-(v)) ≤ |R|· (4 · |R| + |C| · 2) ∈𝒪(k^2),

where the final inclusion uses |C|=k and |R|∈𝒪(k).


*



Let ≺^e be a compatible edge ordering for the restriction of Λ^* to its nonhorizontal edges and let ≺^l be the restriction of ≺^e to the edges that are incident to leafs.
We will now label every used channel with a set of numbers corresponding to the edges that use it in Λ^*:
let c be a used channel. We label c with the number i if and only if  the ith edge in ≺^l uses c.
Note that a channel can be assigned multiple labels.
Let m be the number of leaves. For every 1 ≤ i ≤ m, we define 𝒰_i 
to be all channels labeled with two (not necessarily distinct) j, j' fulfilling j ≤ i ≤ j'; see <ref> for examples.
Let 𝒰=(𝒰_1, 𝒰_2, …, 𝒰_m) denote the resulting sequence.



    𝒰 is a traversal sequence.

We will now show that the sequence 𝒰 is a traversal sequence.
To show Property <ref>,
let i∈ [m] and let c=(v,r,R)∈𝒰_i and c'=(v',r',R')∈𝒰_i
		with v≠ v'.
		Assume towards a contradiction that the line L_γ(v) intersects the interior of the union of R'.
		Let r_i denote a cell of R' that is intersected by L_γ(v) and let e denote the edge that corresponds to the left boundary of r_i.
		Assume without loss of generality that r_i lies to the right of v.
		Note that every edge incident to v precedes e in ≺^e.
		Moreover, every edge that intersects the interior of r_i succeeds e.
		Hence, every edge using c precedes every edge using c' in ≺^l.
		Since c∈𝒰_i, it contains a label that is at least i and, hence, it follows that all labels in c' are strictly larger than i;
		a contradiction to the fact that c'∈𝒰_i.
		Therefore, Property <ref> is satisfied.

To show  Property <ref>, let c be a (used) channel that occurs in 𝒰 and let a be the lowest index with 
c ∈𝒰_a and let b be the highest index with c ∈𝒰_b.
Then for every a ≤ i ≤ b, c ∈𝒰_i by construction and  Property <ref> is fulfilled.

Therefore, 𝒰 is indeed a traversal sequence.



    𝒰 is compatible with Λ^*.

We will now show the compatability of 𝒰 with Λ^*.

Let c be a used channel. Then there exists at least one edge e using c in Λ^*. Let i be the index of e in ≺^l.
Then, by construction, c ∈𝒰_i.
Moreover, by construction, 𝒰 does not contain any channels that are not used.
Therefore,  Property <ref> is satisfied.

To establish Property <ref>,

let e, e' be two edges that are incident to leaves with e ≺^l e', let c be the channel used by e in Λ^* and let c' be the channel used by e' in Λ^*.
Let further i, i' be the indices of e,e', respectively, in the ordering corresponding to ≺^l.
Then i < i' and c ∈𝒰_i and c' ∈𝒰_i' by construction and, therefore,  Property <ref> is satisfied. 

To establish Property <ref>,
let c_1,c_2∈ U_used such that for every edge e_1 using c_1 and for every edge e_2 using c_2, we have e_1 ≺^e e_2.
Let i be the largest index of an edge in c_1 with respect to ≺^l
and let j be the smallest index of an edge in c_2 with respect to ≺^l.
Note that i<j and, by construction, the interval in which c_1 is active ends with 𝒰_i and the interval in which c_2 is active starts with 𝒰_j.
Therefore, there is no index at which both c_1 and c_2 are active and c_1 is active before c_2, which establishes Property <ref>.

To establish Property <ref>,
consider two used channels c_1, c_2 such that c_2 is being used by an edge e that succeeds all edges that use c_1 in ≺^e.
Let i be the index of e with respect to ≺^l. 
Then c_2 ∈𝒰_i and c_1 ∉𝒰_i by construction (and c_1 is active before c_2 by Property <ref>), which establishes Property <ref>.

Therefore, 𝒰 is indeed compatible with Λ^*.




    Bounding the length of the sequence.

Note that if there are two consecutive sets 𝒰_i,𝒰_i+1 in 𝒰 with 𝒰_i=𝒰_i+1, then we can remove one of them and the resulting sequence 𝒰' is still a traversal sequence that is compatible with Λ^*, e.g, in <ref> the set 𝒰_8 can be removed.
Repeat this process to eliminate all consecutive pairs of identical sets 𝒰_i and denote the resulting sequence by 𝒰”.
Since the number of channels in 𝒰” is 𝒪(k^2) by <ref>
and the sets containing a channel form an interval by Property <ref>, it follows that the length of 𝒰” is 𝒪(k^2).



    Algorithm.

So far, we have shown that there is a constant a such that there is a traversal sequence compatible with Λ^* of length at most ak^2.
Moreover, we know that there is a constant b such that |U|≤ bk^2 by <ref>.
Every traversal sequence of length at most ak^2 is uniquely described by specifying for each channel c∈ U at which index in {1,2,…,ak^2} its interval (cf. Property <ref>) starts and at which index it ends (when the starting index  is larger than the ending index, c does not appear in the sequence).
Hence, there are at most (ak^2)^(2bk^2)≤ 2^𝒪(k^2log k) candidate sequences.
Testing whether a candidate sequence is a traversal sequence is easily done in polynomial time and the existence of 𝒰” implies that at least one of the sequences is a traversal sequence that is compatible with Λ^*.


*



Assume towards a contradiction that 𝒰_i contains
two channels c=(w,r,R) and c'=(w,r',R') that can be used by v.
Then there are two cells a∈ R∖ R' and a'∈ R'∖ R such that there is a horizontal line intersecting both a and a'.
This implies that the precondition of Property <ref> is fullfilled and
the conclusion of Property <ref> implies that c,c' are not both contains in 𝒰_i, which yields the desired contradiction.


*



Suppose, inductively, we have obtained insertion sequences
 𝒬_0, 𝒬_1,…,𝒬_q
 for i, s and 𝒰
 such that for each of them
the interval and the dominance properties are fulfilled
and
such that 𝒬_k is a prefix of 𝒬_k+1 for  all 0 ≤ k ≤ q-1.
Note that if q = 0, then 𝒬_0 = () 
is an insertion sequence with the desired properties.
Let 
𝒬_q = (Q_1, Q_2, …, Q_q), 0 ≤ q < |V_i ∩ V_=1|.
Our goal is to construct the sequence 𝒬_q+1.



    Existence of choosable vertices.

We first show that there is a choosable vertex v with regard to 𝒬_q.
To this end, it suffices to show that there exists at least one pair (v,j) such that (Q_1, Q_2, …, Q_q, (v,j)) is an insertion sequence for i, s, and 𝒰
(note that this does not necessarily imply that v is choosable, but its existence implies that there is a choosable vertex, as desired).

Let v be the left-most leaf on level i in Λ^* that is not contained in 𝒬_q and let c be the channel used by v (in Λ^*). 
Let j be the largest index such c ∈𝒰_j, which exists by Property <ref>.
Note that if q=0, the definition of v implies that (v,j) can be appended to the (empty) sequence 𝒬_q to obtain an insertion sequence for i, s, and 𝒰, as desired.
So assume otherwise, i.e., q ≥ 1.
Let Q_q=(v_q,j_q).

Our main goal is now to show that j_q≤ j, which is a necessary condition for appending  (v,j) to 𝒬_q.

Towards a contradiction, assume j < j_q.
Let j^* be the largest index that occurs in 𝒬_q and where j^* ≤ j
(if no such index exists, we define j^*=0).
Let q^* be the largest index such that Q_q^* contains j^*
(if j^*=0, we define q^*=0).


We will now argue that (v,j) can be appended to 𝒬_q* to obtain an insertion sequence for i, s and 𝒰,
which we will then use to argue that 𝒬_q does not satisfy the interval property, yielding the desired contradtion.

So let 𝒬_q^* +1 be the sequence obtained from 𝒬_q^* by appending (v, j).
Clearly, Properties <ref>, <ref>, <ref>, and <ref> are satisfied for the sequence 𝒬_q^* +1.
To see that  Property <ref> also holds,
assume towards a contradiction that there is a vertex v∈ V_i ∩ V_=1 with v≺_i v that is not contained in 𝒬_q^* +1.
By the definition of v, the vertex v is contained in 𝒬_q.
Without loss of generality, assume that v is the first vertex in 𝒬_q with these properties.
Let (v,j)∈𝒬_q.

The constraint v≺_i v implies together with Property <ref>
that there exists an index j'≤ j
such that the
channel c used by v (in Λ^*) is contained in
𝒰_j'.
To obtain the desired contradiction (to the existence of v), we will now show that 
(v,j') is can be appended to 
𝒬_q^* to obtain an insertion sequence for i, s and 𝒰.

Since v∈𝒬_q and v∉𝒬_q^*, it follows that j^*<j (by definition of j^*).
Further, since (again by definition of j^*) there is no index j̃ that occurs in 𝒬_q and where j^*<j̃≤ j, it follows that j < j.
Due to the dominance property for v in 𝒬_q,
j is at most as large as the largest index j_c  for which c∈𝒰_j_c.
To summarize, j'≤ j<j≤ j_c.

By Property <ref> and since c∈𝒰_j' and c∈𝒰_j_c and j'≤ j<j≤ j_c, it follows that c∈𝒰_j.
Then, since v is the first vertex in 𝒬_q with v∈ V_i ∩ V_=1 with v≺_i v that is not contained in 𝒬_q^* +1,
it follows that (v,j) can be appended to 𝒬_q^*
without violating Property <ref> to obtain an insertion sequence for i, s, and 𝒰.
Moreover, note that j<j_q^*+1 where Q_q^*+1=(v_q^*+1, j_q^*+1) and, hence v_q^*+1 is not choosable with regard to 𝒬_q^*, which yields a contradiction to the interval property for v_q^*+1 in 𝒬_q.
Therefore, the vertex v∈ V_i ∩ V_=1 with v≺_i v that is not contained in 𝒬_q^* +1 cannot exists an, hence, Property <ref> is satisfied by 𝒬_q^* +1, which, finally, shows that 𝒬_q^* +1 is an insertion sequence i, s and 𝒰.

Once again, note that j<j_q^*+1 where Q_q^*+1=(v_q^*+1, j_q^*+1) and, hence v_q^*+1 is not choosable with regard to 𝒬_q^*, which yields a contradiction to the interval property for v_q^*+1 in 𝒬_q.
Therefore j_q≤ j.
The fact that j_q≤ j can be combined with the definition of v to obtain that
(Q_1, Q_2, …, Q_q, (v,j)) is indeed an insertion sequence for i, s, and 𝒰, as claimed, and, thus, there exists at least one choosable vertex with regard to 𝒬_q.



    Interval property.

Now let v be a choosable vertex together with an smallest index j such that 𝒬_q+1 = (Q_1, Q_2, …, Q_q, Q_q+1 = (v,j)) 
is an insertion sequence for i, s, and 𝒰.
We will now show that it satisfies the interval property.
Let v' ∈ V_i ∩ V_=1 be a vertex. We will show that the interval property is fulfilled for v'.
We distinguish four cases.



    Case 1:
 v' = v. Then, v' has been choosable in 𝒬_q in an interval ending with q and v∈ Q_q+1, thus the interval 
property is fulfilled.



    Case 2:
 v'∈𝒬_q. Hence, v'∈𝒬_q+1 and, thus, it is not choosable for 𝒬_q+1, and the interval property is fulfilled for 𝒬_q+1 
since it was already fulfilled in 𝒬_q.



    Case 3:
 The interval in which v' was choosable in 𝒬_q is empty.
Then the interval in which v' is choosable in 𝒬_q+1 has length at most one and if it has length exactly one, it is choosable only with regard to 𝒬_q+1, hence, the interval property is fulfilled.



    Case 4:
 v' is not contained in 𝒬_q and the interval in which v' was choosable in 𝒬_q is nonempty and ends with q.
We need to show that v' is choosable with regard to 𝒬_q+1.

There exists a channel c' in U_j that can be used by v' since we could have appended v' with the same index as we included v.
Further, there exists no constraint of the form v' ≺_i v or v ≺_i v', otherwise one of them would have not been choosable with regard to 𝒬_q as appending it would have 
violated Property <ref> of the resulting insertion sequence.
Let 𝒬_q+2 denote the sequence obtained by appending (v', j) to 𝒬_q+1.
We claim that 𝒬_q+2 is an insertion sequence.
Indeed, Property <ref> is fulfilled, since v' was not in  𝒬_q+1. 
Property <ref> is fulfilled for 𝒬_q+2 since v' and v both were appended with index j.
We already stated that v' can use a channel c' in U_j, therefore, Property <ref> is fulfilled.
Property <ref> is fulfilled since v' was choosable with regard to 𝒬_q+1.
Property <ref> is fulfilled for 𝒬_q+2 since the unique usable channel c' in U_j that is used by v' in 𝒬_q+2 does not change.

This shows that v' is still choosable with regard to 𝒬_q+1, and the interval property is fulfilled.

So in any case, the interval property for 𝒬_q+1 is fulfilled.



    Dominance property.

It is left to show that the dominance property is fulfilled for 𝒬_q+1.
For all vertices in 𝒬_q+1 but v, the dominance property carries over from 𝒬_q.

Let v_ℓ' ∈ V_i ∪ V_=1 and let e (e_ℓ') be the edge incident to v (v_ℓ') with e ≺^l_i e_ℓ' or v  = v_ℓ'. 
We have to show that j ≤ j', where j' is the maximum index such that the channel c' used by v_ℓ' (in Λ^*) is in 𝒰_j'.
We distinguish two cases:



    Case 1:
 v = v_ℓ'. 
Assume towards contradiction that j' < j and let j^* be the largest index such that j^* is present in 𝒬_q and j^* ≤ j'
(if such an index does not exists, we define j^*=0).
Further, let q^* be the largest index such that Q_q^* contains index j^* (and q^*=0 if j^*=0).

Let 𝒬_q^* + 1 be the sequence obtained from 𝒬_q^* by appending (v, j').
We will show 𝒬_q^* + 1 is an insertion sequence for i, s, and 𝒰,
 which gives us a contradiction to the interval property of v_q^*+1, where v_q^*+1∈ Q_q^*+1 (since it is not choosable with regard to 𝒬_q^*).
 
Clearly, Properties <ref>, <ref>, <ref>, and <ref> are fulfilled for 𝒬_q^* + 1.
It remains to establish Property <ref>.
Since v is choosable in 𝒬_q, all vertices w∈ V_i ∪ V_=1 with w ≺_i v are already in 𝒬_q and, thus, the dominance property is fulfilled for them in 𝒬_q. Let w be such a vertex, let j_w be the index with which w is contained in 𝒬_q and let e_w be the edge incident to w. Clearly, e_w ≺^l_i e.
Hence, by the dominance property of w, it follows j_w ≤ j' (and also j_w ≤ j^* since j_w is present in 𝒬_q) and therefore, w is contained in 𝒬_q^*.
Thus, Property <ref> is also fulfilled and 𝒬_q^* +1 is indeed an insertion sequence.

This is a contradiction to the interval property of v_q^*+1, where v_q^*+1∈ Q_q^*+1 since it is not choosable with regard to 𝒬_q^*.
Thus, j' ≤ j, as desired.



    Case 2:
 e ≺^l_i e_ℓ'.
Assume towards contradiction that j' < j.
Because of Case 1, we know that j is at most as large as the largest index of the channel c used by v (in Λ^*) and, hence j' is strictly smaller than this index.
 Also because of Property <ref>, we know that there exists an index j̃ with j̃≤ j' and c ∈𝒰_j̃, thus, by Property <ref>, we know that c ∈𝒰_j'. 

Now let j^* be the largest index such that j^* is present in 𝒬_q and j^* ≤ j'
(if such an index does not exists, we define j^*=0).
Further, let q^* be the largest index such that Q_q^* contains index j^* (and q^*=0 if j^*=0).
Let 𝒬_q^* + 1 be the sequence obtained from 𝒬_q^* by appending (v, j').
We will show 𝒬_q^* + 1 is an insertion sequence for i, s, and 𝒰,
which gives us the desired
contradiction to the interval property of v_q^*+1, where v_q^*+1∈ Q_q^*+1 (since it is not choosable with regard to 𝒬_q^*).

Clearly, Properties <ref>, <ref>, <ref>, and <ref> are fulfilled for 𝒬_q^* + 1.
It remains to establish Property <ref>.
Since v is choosable in 𝒬_q, all vertices w∈ V_i ∪ V_=1 with w ≺_i v are already in 𝒬_q and, thus, the dominance property is fulfilled for them. 
Let w be such a vertex, let j_w be the index with which w is contained in 𝒬_q and let e_w be the edge incident to w. Clearly, e_w ≺^l_i e ≺^l_i e_ℓ'.
Hence, by the dominance property of w, it follows j_w ≤ j' (and also j_w ≤ j^* since j_w is present in 𝒬_q) and therefore, w is contained in 𝒬_q^*.
Thus, Property <ref> is also fulfilled and 𝒬_q^* +1 is indeed an insertion sequence.

This is a contradiction to the interval property of v_q^*+1, where v_q^*+1∈ Q_q^*+1 since it is not choosable with regard to 𝒬_q^*.
Thus, j' ≤ j, as desired.

Therefore, the dominance property is satisfied.



    Algorithm.

We have shown that we can generate  𝒬_|V_i ∩ V_=1| by starting with an empty sequence 𝒬_0 = () and appending choosable 
vertices until all leaves of level i are contained in the insertion sequence (the insertion sequence illustrated in <ref> was created by means of this algorithm). Clearly, testing whether a vertex is choosable can be done in polynomial 
time, therefore we can generate 𝒬_|V_i ∩ V_=1| in polynomial time as well.


*



For every level i∈ [h], draw the ears in the unique way described by s^i, which can be done without creating any crossings.
Let Λ_core^t, e denote the resulting drawing.

We now add the leaves to Λ_core^t, e according to the insertion sequences as follows.
We consider all indices ℓ∈ [m] in increasing order.
To process an index ℓ, we consider all levels i∈ [h] in increasing order.
To process a level i,
we consider the indices q∈ [q^i] in increasing order.
To process the index q, 
let Q^i_q = (v^i_q, j^i_q) be the q-th entry of the insertion sequence 𝒬^i. If j^i_q = ℓ,
let c=(w,r,R) be unique channel
usable by v in 𝒰_ℓ.
If R consists of a single cell (namely, r) that contains transition vertices, we just assign v to r, without drawing it yet.
Assigned vertices will be drawn in a post-processing step.
Otherwise, i.e., if r is not a cell that contains transition vertices
, we draw a (nearly horizontal) line from w to the right boundary of the union of R, then traverse along upwards or downwards  along this boundary until we reach the y-coordinate γ(v).

Assume that we have already performed some number of steps of the algorithm while maintaining the following invariants:


  * The current drawing is crossing-free;

  * For each level i,
 the leaves already present  in the drawing (which do not include the assigned leaves)
are in the same order as in 𝒬^i; and

  * Let v be a leave that is already present or assigned and let Q^i_ℓ=(v,j)∈𝒬^i.
Further, let c=(w,r,R) be the unique channel usable by v in 𝒰_j.
Then v is either drawn in c or assigned to r.


Let (v,j) be the tuple that is processed in the next step and let c=(w,r,R) be the unique channel in 𝒰_j that can be used by v.
If R consists of a single cell (namely, r) that contains transition vertices, the invariants are obviously maintained.
Otherwise, if r does not contain transition vertices, the curve along which the algorithm draws the edge incident to v is not crossed by any of the previously drawn edges by Property <ref> and Property <ref> of the traversal sequence and, hence, Invariant 1 is maintained.
For Invariant 2, assume towards a contradiction that there is an already inserted leaf w that is to the right of v.
By construction, it is in a cell that is to the right of the one of v. This is a contradiction to Property <ref>.
Clearly, Invariant 3 is satisfied.

Hence, the invariants are maintained.
Let Λ denote the resulting drawing.
It remains to draw the unassigned leaves.
For each level i and for each cell r with transition vertices on level i, we simply perform a topological sort with respect to ≺_i on all vertices in r (which are assigned leaves and transition vertices)
and then place them according to the obtained order (possibly rearranging the order of the transition vertices in r), which is easy to do without introducing crossings.
Let Λ' denote the final drawing, which is cross-free.

It remains to show that in Λ' all constraints are respected.
By construction, this is the case for the vertices in Λ_core^t, e.

So let v be a leaf on level i, let c be the channel used by v in Λ'.
All constraints between v and other leaves are respected as all leaves on level i appear in the same order as in 𝒬^i up to permutations in transition vertex cells according to topological orderings with respect to ≺_i.
Constraints between v and non-leafs are satisfied by Property <ref>.

Clearly, all steps of the algorithm can be carried out in polynomial time.


*



We begin by augmenting Λ_core^t 
as described in the beginning of the proof of <ref>, which is easy to do in polynomial time.
The decomposition into cells can also easily be constructed in polynomial time.
We then use 
<ref>
to construct a set of 2^𝒪(k^2log k) candidate traversal sequences of length at most 𝒪(k^2) that is guaranteed to contain a traversal sequence that is compatible with Λ^*
in
2^𝒪(k^2log k)n^𝒪(1)
time.

For each of these candidate sequences, we now try to construct a valid ear orientation together with an insertion sequence for each level.
To do this for a given level i, we enumerate all (at most 2^2k) valid ear orientations
for level i
in
2^2kn^𝒪(1) time.
For each of these valid ear orientations, 
 we then try to apply the algorithm corresponding to <ref> to obtain an insertion order, which takes polynomial time per ear orientation.
 
If we succeed in finding a valid ear orientation together with an insertion sequence for each level, we now try to apply the algorithm corresponding to <ref> to construct the desired drawing, which takes polynomial time.

If we fail at any point along the way, we just continue with the next candidate traversal sequence.

Since our candidate set contains a traversal sequence that is compatible with Λ^*, we are guaranteed to eventually obtain the desired drawing.
In particular, when applying our strategy to the compatible sequence, we are guaranteed to obtain a valid ear orientation (not necessarily the one used in Λ^*) together with an insertion sequence for each level,
which allows us to successfully apply the algorithm corresponding to <ref>.
We remark that if the algorithm corresponding to <ref> successfully terminates, it is guaranteed to return an insertion sequence for the given valid ear orientation.
Moreover, we emphasize that <ref> does not require that the ear orientations are the ones used in Λ^*, meaning that our strategy is not invalidated by the fact that algorithm corresponding to <ref> might output an insertion sequence even if the given valid ear orientation is not the one used in Λ^*.
The total runtime of the algorithm is 2^𝒪(k^2log k)n^𝒪(1), as claimed.


*



In view of <ref>, we may assume that 𝒢 has no isolated vertices.
Assume that there is a constrained level planar drawing Γ^* of 𝒢. 
We begin by applying <ref>, that is, we construct a family ℱ of 2^𝒪(klog k) drawings 
for which there exists a refined visibility extension Λ^* of Γ^* such that the subdrawing Λ_core of Λ^* induced by the core of Λ^* with respect to C is contained in ℱ.
For each drawing in ℱ, we try to apply the algorithm corresponding to <ref> to insert the transition vertices in polynomial time.
If successful, we then try to apply the algorithm corresponding to <ref> to construct the desired drawing in 2^𝒪(k^2log k)· n^𝒪(1) time.
If successful, we report the drawing.
If we fail at any point along the way, we just continue with the next drawing in ℱ.
Given that ℱ contains Λ_core, we are guaranteed to eventually obtain the desired drawing.
In contrast, if 𝒢 does not admit a constrained level planar drawing, the described algorithm is guaranteed to fail in every iteration, in which case we correctly report that the desired drawing does not exists.
The total runtime is 2^𝒪(k^2log k)· n^𝒪(1).


