The Parameterized Complexity of Extending Stack Layouts
Thomas Depian Simon D. Fink Robert Ganian Martin Nöllenburg


long

longtrue 
long
    prooflaterm
    proofsketcho +b
    
    statelaterm

    prooflaterm +b
        
        #1#2
    
    proofsketchOProof sketch.
    
    
    

    statelaterm +b
        #1#2
    














=1 


./graphics/

plainurl



 


The Parameterized Complexity of Extending Stack Layouts 

Algorithms and Complexity Group, TU Wien, Vienna, Austriatdepian@ac.tuwien.ac.athttps://orcid.org/0009-0003-7498-6271

Algorithms and Complexity Group, TU Wien, Vienna, Austriasfink@ac.tuwien.ac.athttps://orcid.org/0000-0002-2754-1195

Algorithms and Complexity Group, TU Wien, Vienna, Austriarganian@ac.tuwien.ac.athttps://orcid.org/0000-0002-7762-8045

Algorithms and Complexity Group, TU Wien, Vienna, Austrianoellenburg@ac.tuwien.ac.athttps://orcid.org/0000-0003-0454-3937



T. Depian, S. D. Fink, R. Ganian, M. Nöllenburg 

Thomas Depian, Simon D. Fink, Robert Ganian, Martin Nöllenburg 


[500]Theory of computation Fixed parameter tractability
[500]Mathematics of computing Graphs and surfaces

 

 


long


[cite=]Full versionhttps://arxiv.org/abs/2409.XYZ





All authors acknowledge support from the Vienna Science and Technology Fund (WWTF) [10.47379/ICT22029]. Robert Ganian and Thomas Depian furthermore acknowledge support from the Austrian Science Fund (FWF) [10.55776/Y1329].








Stefan Felsner and Karsten Klein
2
32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)
GD 2024
GD
2024
September 18–20, 2024
Vienna, Austria

320
10


















arrows.meta,patterns,ipe












reduction-ruleReduction Rule
propertyProperty














































































propertyPropertyProperties
propertyPropertyProperties
FPFPFPs
FPFPFPs
ECECECs
ECECECs






The Parameterized Complexity of
Extending Stack Layouts
    Martin Nöllenburg
    Accepted Sep 3 2024 to ApJ Letters

=======================================================




§ ABSTRACT 
An ℓ-page stack layout (also known as an ℓ-page book embedding) of a graph is a linear order of the vertex set together with a partition of the edge set into ℓ stacks (or pages), such that 
the endpoints of no two edges on the same stack alternate.
We study the problem of extending a given partial ℓ-page stack layout into a complete one, which can be seen as a natural generalization of the classical -hard problem of computing a stack layout of an input graph from scratch. Given the inherent intractability of the problem, we focus on identifying tractable fragments through the refined lens of parameterized complexity analysis. 
Our results paint a detailed and surprisingly rich complexity-theoretic landscape of the problem which includes the identification of para-hard, [1]-hard and -tractable, as well as fixed-parameter tractable fragments of stack layout extension via a natural sequence of parameterizations.





§ INTRODUCTION


An ℓ-page stack layout (or ℓ-page book embedding) of a graph G consists, combinatorially speaking, of (i) a linear order ≺ of its vertex set V(G) and (ii) a partition σ of its edge set E(G) into ℓ≥ 1 (stack-)pages such that for no two edges (with distinct endpoints) uv and wx with u ≺ v and w ≺ x that are assigned to the same page their endpoints alternate in ≺, i.e., we have 
u ≺ w ≺ v ≺ x. 
When drawing a stack layout, the vertices are placed on a line called the spine in the order given by ≺ and the edges of each page are drawn as pairwise non-crossing arcs in a separate half-plane bounded by the spine, see <ref>a. 




Stack layouts are a classic and well-studied topic in graph drawing and graph theory <cit.>. 
They have immediate applications in graph visualization <cit.> as well as in bioinformatics, VLSI design, and parallel computing <cit.>; see also the overview by Dujmović and Wood <cit.>.


The minimum number ℓ such that a given graph G admits an ℓ-page stack layout is known as the stack number, page number, or book thickness of G. 


While the graphs with stack number ℓ=1 are the outerplanar graphs, which can be recognized in linear time, the problem of computing the stack number is -complete in general.
Indeed, the class of graphs with stack number ℓ≤ 2 are precisely the subhamiltonian graphs (i.e., the subgraphs of planar Hamiltonian graphs) and recognizing them is -complete <cit.>.

Computing the stack number is known to also remain -complete if the vertex order is provided as part of the input and ℓ=4 <cit.>, and overcoming the intractability of these problems has been the target of several recent works in the field <cit.>.




Many other results on stack layouts are known—for instance, every planar graph has a 4-page stack layout and this bound is tight <cit.>. 
For a comprehensive list of known upper and lower bounds for the stack number of different graph classes, we refer to the collection by 
Pupyrev <cit.>.







In this paper, we take a new perspective on stack layouts, namely the perspective of drawing extensions. 
In drawing extension problems, the input consists of a graph G together with a partial drawing of G, i.e., a drawing of a subgraph H of G. 
The task is to insert the vertices and edges of G which are missing in H in such a way that a desired property of the drawing is maintained; see <ref>b for an example. 
Such drawing extension problems occur, e.g., when visualizing dynamic graphs in a streaming setting, where additional vertices and edges arrive over time and need to be inserted into the existing partial drawing. 

Drawing extension problems have been investigated for many types of drawings in recent years—including planar drawings <cit.>, upward planar drawings <cit.>, level planar drawings <cit.>, 1-planar drawings <cit.>, and planar orthogonal drawings <cit.>—but until now, essentially nothing was known about the extension of stack layouts/book embeddings.


Since it is -complete to determine whether a graph admits an ℓ-page stack layout (even when ℓ is a small fixed integer), the extension problem for ℓ-page stack layouts is -complete as well—after all, setting H to be empty in the latter problem fully captures the former one.
In fact, the extension setting can seemlessly also capture the previously studied -complete problem of computing an ℓ-stack layout with a prescribed vertex order <cit.>; indeed, this corresponds to the special case where V(H) = V(G) and E(H)=∅.


Given the intractability of extending ℓ-page stack layouts in the classical complexity setting, we focus on identifying tractable fragments of the problem through the more refined lens of parameterized complexity analysis <cit.>, which considers both the input size of the graph and some additional parameter k of the instance[We assume familiarity with the basic foundations of parameterized complexity theory, notably including the notions of fixed-parameter tractability, , [1]-, and para-hardness <cit.>.].













    Contributions.

A natural parameter in any drawing extension problem is the size of the missing part of the graph, i.e., the missing number of vertices and/or edges. 
We start our investigation by showing that the Stack Layout Extension problem () for instances without any missing vertices, i.e., V(G) = V(H), is fixed-parameter tractable when parameterized by the number of missing edges |E(G)∖ E(H)| (<ref>).

The above result, however, only applies in the highly restrictive setting where no vertices are missing—generally, we would like to solve instances with missing vertices as well as edges. 
A parameterization that has been successfully used in this setting is the vertex+edge deletion distance, i.e., the number of vertex and edge deletion operations[As usual, we assume that deleting a vertex automatically also deletes all of its incident edges.] required to obtain H from G. But while this parameter has yielded parameterized algorithms when extending, e.g., 1-planar drawings <cit.> and orthogonal planar drawings <cit.>, we rule out any analogous result for  by establishing its -completeness even if H can be obtained from G by deleting only two vertices (<ref>). This means that more “restrictive” parameterizations are necessary to achieve tractability for the problem of extending ℓ-page stack layouts.


Since the missing vertices in our hardness reduction have a high degree, we then consider parameterizations by the combined number of missing vertices and edges κ = V(G) ∖ V(H) + E(G)∖ E(H).
We show that  belongs to the class  when parameterized by κ (<ref>) while being [1]-hard (<ref>), which rules out the existence of a fixed-parameter tractable algorithm under standard complexity assumptions.
The latter result holds even if we additionally bound the page width ω of the stack layout of H,  which measures the maximum number of edges that are crossed on a single page by a line perpendicular to the spine <cit.>.

On our quest towards a fixed-parameter tractable fragment of the problem, we thus need to include another restriction, namely the number ℓ of pages of the stack layout. 
So finally, when parameterizing  by the combined parameter κ + ω + ℓ, we show that it becomes fixed parameter tractable (<ref>). 
Our results are summarized in <ref>.

long
Due to space constraints, full proofs of statements marked by  are deferred to the appendix.






















































































§ PRELIMINARIES


We assume the reader to be familiar with standard graph terminology <cit.>.

Throughout this paper, we assume standard graph representations, e.g., as double-linked adjacency list, that allow for efficient graph modifications.
For two integers p ≤ q we denote with [p, q] the set {p, p+1, …, q} and use [p]_0 and [p] as abbreviations for [0, p] and [1, p], respectively.
Let G be a graph that is, unless stated otherwise, simple and undirected, with vertex set V(G) and edge set E(G).

For X⊆ V(G), we denote by G[X] the subgraph of G induced on X. 





    Stack Layouts.

For an integer ℓ≥ 1, an ℓ-page stack layout of G is a tuple G where ≺_G is a linear order of V(G) and σ_G  E(G) → [ℓ] is a function that assigns each edge to a page p ∈ [ℓ] such that  
for each pair of edges u_1v_1 and u_2v_2 with σ(e_1) = σ(e_2) it does not hold u_1 ≺ u_2 ≺ v_1 ≺ v_2.
For the remainder of the paper, we write ≺ and σ if the graph G is clear from context.
We call ≺ the spine (order) and σ the page assignment. 

Observe that we can interpret a stack layout as a drawing of G on different planar half-planes, one per page p ∈ [ℓ], each of which is bounded by the straight-line spine delimiting all half-planes.  
One fundamental property of a stack layout is its page width—denoted as  or simply ω if  is clear from context—which is the maximum number of edges that are crossed on a single page by a line perpendicular to the spine <cit.>.
The properties of stack layouts with small page width have been studied, e.g., by Stöhr <cit.>.




We say that two vertices u and v are consecutive on the spine if they occur consecutively in ≺.


A vertex u ∈ V(G) sees a vertex v ∈ V(G) on a page p ∈ [ℓ] if there does not exist an edge e = xy ∈ E(G) with σ(e) = p and x ≺ u ≺ y ≺ v or u ≺ x ≺ v ≺ y.
Note that if u sees v, then v also sees u.
For two vertices u and v which are consecutive in ≺, we refer to the  segment 

on the spine between u and v as the interval between u and v, denoted as [u, v].



    Problem Statement.

Let H ⊆ G be a subgraph of a graph G.

We say that G is an extension of H if σ_H⊆σ_G and ≺_H⊆≺_G.







We now formalize our problem of interest:


 ()Integer ℓ≥ 1, graph G, subgraph H of G, and ℓ-page stack layout H.Does there exist an ℓ-page stack layout G of G that extends H?

We remark that while is defined as a decision problem for complexity-theoretic reasons, every algorithm presented in this article is constructive and can be trivially adapted to also output a layout G as a witness (also called a solution) for positive instances. For an instance  of , we use  as shorthand for |V(G)|+|E(G)|+ℓ.

In line with the terminology previously used for drawing extension problems <cit.>, we refer to the vertices and edges in V(H)∪ E(H) as old and call all other vertices and edges of G new.
Let  and  denote the sets of all new vertices and edges, respectively, and set  and . Furthermore, we denote with the set of new edges incident to two old vertices, i.e., {e = uv ∈| u, v ∈ V(H)}.
We consider the parameterized complexity of our extension problem by measuring how “incomplete” the provided partial solution is using the following natural parameters that have also been used in this setting before <cit.>:
the vertex+edge deletion distance, which is +, and the total number of missing vertices and edges, i.e., +. 
































§  WITH ONLY MISSING EDGES IS 


We begin our investigation by first analyzing the special case where V(G)=V(H), i.e., when only edges are missing from H. We recall that the problem remains -complete even in this setting, as it generalizes the problem of computing the stack number of a graph with a prescribed vertex order <cit.>.
Furthermore, both of the aforementioned measures of the incompleteness of H are the same and equal =. 
As a “warm-up” result, we show that in this setting  is fixed-parameter tractable parameterized by .

Towards this, consider the set S(e) ⊆ [ℓ] of pages on which we could place a new edge e without introducing a crossing with edges from H; formally, p∈ S(e) if and only if ⟨≺_H,σ_H∪(e,p)⟩ is an ℓ-page stack layout of H∪{e}.
Intuitively, if S(e) is large enough, then we are always able to find a 
“free” page to place e independent of the placement of the remaining new edges.
Formally, one can easily show:














lem:only-edges-remove-easy-edgeslemmalemmaOnlyEdgesRemoveEasyEdges
    
	Let = be an instance of  with = ∅ that contains an edge e ∈ with S(e)≥.
	The instance ' = (ℓ, H, G', ) with G' = G ∖{e} is a positive instance if and only if  is a positive instance.

plemmaOnlyEdgesRemoveEasyEdges
    First, note that removing an edge from G and adapting the page assignment σ accordingly does not invalidate an existing solution  to  for .
	Hence, the “(⇐)-direction” holds trivially, and we focus on the “(⇒)-direction”.
	
	*(⇒)
	Let ' be a positive instance of  with the solution .
	By our selection of e, there exists a page p ∈ S(e) such that we have for every edge e' ∈ with e' ≠ e that σ(e') ≠ p holds.
	We take  and extend σ by the page assignment (e, p) to obtain G.
	By the definition of S(·), this cannot introduce a crossing with edges from H and by our selection of p, no crossings with other edges from  are possible either.
	Hence, G is a valid stack layout of G that extends H as we did not alter  except extending the page assignment.
    Thus, it witnesses that  is a positive instance of .

With <ref> in hand, we can establish the desired result:

thm:only-edges-fpttheoremtheoremOnlyEdgesFPT
	
	
    
    Let = be an instance of  with = ∅.
	We can find an ℓ-page stack layout of G that extends  or report that none exists in ^· time.
 
 


	We compute for a single edge e ∈ the set S(e) in linear time by checking with which of the old edges e would cross.
	If S(e) ≥, then following <ref>, we remove e from G.
	Overall, this takes · time and results in a graph G' with H ⊆ G' ⊆ G.
	Furthermore, each remaining new edge e' ∈ E(G') ∖ E(H) can be put in fewer than  different pages.
	Hence, we can brute-force over all the at most ^ page assignments σ' that extend σ_H for all edges in E(G') ∖ E(H), and for each such assignment we check in linear time whether no pair of edges e', e”∈ E(G')∖ E(H) cross each other.

ptheoremOnlyEdgesFPT
	We compute for a single edge e ∈ the set S(e) in linear time by checking with which of the old edges e would cross.
	If S(e) ≥, then we remove e from G.
	Overall, this takes · time and results in a graph G' with H ⊆ G' ⊆ G.
	Furthermore, each edge e' ∈ E(G') ∖ E(H) can be put in fewer than  different pages.
	Hence, we can brute force the possible page assignments for each new edge e'.
	Each of the resulting ^ different ℓ-page stack layouts  is by construction an extension of H.
	Creating  can be done by copying H and then augmenting it with  new edges.
	
	This amounts to  time.
	For each created ℓ-page stack layout, we can check in linear time whether it is crossing free. 
	Note that by our pre-processing step, no new edge can cross an old edge, and thus it suffices to check whether no pair of edges e', e”∈ E(G')∖ E(H) cross each other.
	If there exists a crossing free layout, then applying <ref> iteratively tells us that we can extend it to a solution G for .
	
	
	If none of them is crossing free, we conclude by applying (iteratively) <ref> that  does not admit the desired ℓ-page stack layout.
	Combining all, the overall running time is ^·.





§  WITH TWO MISSING VERTICES IS -COMPLETE


Adding only edges to a given linear layout is arguably quite restrictive.
Therefore, we now lift this restriction and consider  in its full generality, i.e., also allow adding vertices.
Somewhat surprisingly, as our first result in the general setting we show that  is -complete even if the task is to merely add two vertices, i.e., for = 2 and = ∅.
This rules out not only fixed-parameter but also  tractability when parameterizing by the vertex+edge deletion distance, and represents—to the best of our knowledge—the first example of a drawing extension problem with this behavior.

To establish the result, we devise a reduction from  <cit.>.
long
In our reduction, we insert two new vertices into a partial layout derived from the given formula, and use the page assignment of their incident edges to encode a truth assignment and validate that it satisfies all clauses.
For this, we will need to restrict the positions of the new vertices to a certain range along the spine.
In <ref>, we introduce the fixation gadget that ensures this.
We also reuse this gadget in the reduction shown in <ref>.

But first, we use it in this section to perform our reduction and prove -completeness in <ref>.

sectionParaNPIntuition
Let φ = (𝒳, 𝒞) be an instance of  consisting of N variables 𝒳 = {x_1, …, x_N} and M clauses 𝒞 = {c_1, …, c_M}, each consisting of three different and pairwise non-complementary literals.


longIntuitively, theThe
reduction constructs an instance = of  which represents each variable x_i and each clause c_j of φ, respectively, by a corresponding vertex in H.
The linear order ≺_H has the form x_1 ≺ x_2 ≺…≺ x_N ≺ c_1 ≺…≺ c_M; see long<ref><ref>.
Furthermore, contains two new vertices s and v.
The vertex s is adjacent to all variable-vertices and the construction will ensure that the page assignment for its incident edges represents, i.e., selects, a truth assignment Γ for φ.
The vertex v is adjacent to all clause-vertices, and its purpose is to verify that the truth assignment satisfies all clauses.
For the followinglong high-level description of how this is achieved, we assume s ≺ v ≺ x_1 longand will ensure lateras we will use a fixation gadget to ensure that every solution  of  has this property.

To each variable x_i, we associate two pages p_i and p_¬ i corresponding to its possible truth states.
We ensure that s can see each variable-vertex only on its associated pages using edges incident to dummy vertices d_q with q ∈ [N + M + 1].
These dummy vertices are distributed as in long<ref><ref>.
Hence, a page assignment for the edges incident to s induces a truth assignment.
Similar edges also ensure that v can see a clause-vertex c_j only on the pages that are associated to the negation of the literals the clause c_j is composed of, see long<ref>the blue arcs in <ref> for an illustration.
We defer the full construction to <ref>.

long

We now ensure that s ≺ v ≺ x_1 holds in every solution of  by using a fixation gadget on two vertices, i.e., for F = 2.
In particular, we set a_3 ≺ d_1, i.e., we place the fixation gadget at the beginning of the spine, and identify s = f_1 and v = f_2.
The spine order ≺_H is then the transitive closure of all the partial orders stated until now; see <ref>.
Finally, we add the edge d_1d_N + M + 1 and set σ(d_1d_N + M + 1) = p_d to ensure that our construction has <ref>.

Regarding the correctness of our reduction, we make the following observation.

If an induced truth assignment does not satisfy a clause c_j, then it must use the pages associated to the negated literals of c_j.
Thus, the new edge vc_j will cross another edge no matter which page we uselong, see also <ref>.
However, if a clause c_j is satisfied, we can find a page for the edge vc_j that does not introduce a crossing: the page associated to the negation of the literal that satisfies c_j.
Consequently, if φ is satisfiable, then there exists an extension G.
Similarly, the page assignment of an extension G induces a truth assignment Γ that satisfies φ.
long
An intuitive example of the reduction is provided in <ref>, and we obtain the following theorem.




long
Finally, recall that our approach hinges on some way to restrict the new vertices s and v to be placed within a certain range, i.e., before x_1.
We realize this using the fixation gadget that we describe in <ref>.

We also reuse this gadget in the reduction from <ref>.
In <ref>, we show how this can be build into our reduction to prove <ref>.


The graph H that we construct will have multi-edges to facilitate the presentation of the reduction. The procedure for removing multi-edges is detailed in <ref>.

sectionParaNPBaseLayout



 §.§ Encoding the Variables and Clauses: The Base Layout


For each variable x_i and each clause c_j in φ we introduce a vertex in H.
In the following, we use the same symbol to address an element of φ and its representation in H.
Let us first fix the spine order ≺_H.
For every i ∈ [N - 1] and j ∈ [M - 1], we set x_i ≺ x_i + 1 and c_j≺ c_j + 1.
Furthermore, we order the variables before the clauses on the spine, i.e., we set x_N ≺ c_1.
Next, we add N + M + 1 dummy vertices d_q to H and distribute them on the spine.
More concretely, we set d_i ≺ x_i ≺ d_i + 1 and d_N + j≺ c_j ≺ d_N + j + 1 for every i ∈ [N] and j ∈ [M].
By taking the transitive closure of the above order, we obtain the following linear order, which we also visualize in <ref>.

    d_1 ≺ x_1 ≺ d_2 ≺ x_2 ≺…≺ x_N ≺ d_N + 1≺ c_1 ≺…≺ c_M ≺ d_N + M + 1

We now turn our attention to the page assignment σ_H and create for each variable x_i ∈𝒳 the two pages p_i and p_¬ i.
Intuitively, the assignment of an edge incident to x_i to either of these two pages will determine whether x_i is true or false.
For each i, j ∈ [N] with i ≠ j, we create the edges e(x_i, p_j) = d_id_i + 1 and e(x_i, p_¬ j) = d_id_i + 1 in H.
We assign the edge e(x_i, p_j) to the page p_j and the edge e(x_i, p_¬ j) to p_¬ j, i.e., we have σ(e(x_i, p_j)) = p_j and σ(e(x_i, p_¬ j)) = p_¬ j.
<ref> (left) visualizes this.
Note that this introduces multi-edges in H, but recall that we resolve them in <ref>. In particular, we will address these multi-edges in <ref>.
Next, we consider each combination of a clause c_j ∈𝒞 and a variable x_i ∈𝒳.
If x_i does not appear in c_j, we create the edges e(c_j, p_i) = d_N + jd_N + j + 1 and e(c_j, p_¬ i) = d_N + jd_N + j + 1.
Similar to before, we set σ(e(c_j, p_i)) = p_i and σ(e(c_j, p_¬ i)) = p_¬ i.
If x_i appears in c_j without negation, we create the edge e(c_j, p_i) = d_N + jd_N + j + 1 and set σ(e(c_j, p_i)) = p_i.
Symmetrically, if x_i appears negated in c_j, we create the edge e(c_j, p_¬ i) = d_N + jd_N + j + 1 and set σ(e(c_j, p_¬ i)) = p_¬ i.
We visualize this page assignment in <ref> (middle and right).

This completes the base layout of our reduction.
longHowever, we have only defined parts of H and its stack layout  and complete the construction in <ref>. 
Next, we introduce two new vertices s and v in G.
The vertex s is adjacent to each x_i ∈𝒳 and the vertex v is adjacent to each c_j ∈𝒞.
Let us assume for the moment that in every extension G of H we have s ≺ v ≺ d_1.
Then, the vertex s can “see” each x_i ∈𝒳 only on the pages p_i and p_¬ i.
Hence, the page assignment of sx_i can be interpreted as the truth state of x_i.
Similarly, from the perspective of the vertex v, each c_j ∈𝒞 is only visible on the pages that correspond to the complementary literals of c_j.
So intuitively, if the page assignment of the edges incident to s induces a truth assignment that falsifies c_j, then these new edges will block the remaining available pages for the edge vc_j.
Hence, v verifies the truth assignment induced by the edges incident to s, see also <ref>.

longThis indicates the intended semantics of our reduction but has still one caveat: 
We have to ensure that we have s ≺ v ≺ d_1 in every solution to our created instance.Note that this relies on the assumption that we have s ≺ v ≺ d_1. However, we can satisfy this assumption using a fixation gadget.





 §.§ Restricting the Placement of New Vertices: The Fixation Gadget


The purpose of the so-called fixation gadget is to restrict the possible positions of new vertices to given intervals.
As this gadget will also find applications outside this reduction, we describe in the following in detail its general construction for F > 1 new vertices ℱ = {f_1, …, f_F}.


First, we introduce 3(F + 1) new vertices v_1, …, v_F + 1, b_1, …, b_F + 1, and a_1, …, a_F + 1. 

We fix the spine order ≺_H among these vertices 


to 
	b_1 ≺ v_1 ≺ a_1 ≺ b_2 ≺ v_2 ≺ a_2 ≺…≺ b_F + 1≺ v_F + 1≺ a_F + 1; see also <ref>.

Then, every new vertex f_i is made adjacent to v_i and v_i + 1 and we aim to allow these new edges to be placed only in a dedicated further page p_d.
To achieve this, we first introduce for every i ∈ [F + 1] and every page p ≠ p_d an edge e(b_i, a_i, p) = b_ia_i in H and set σ(e(b_i, a_i, p)) = p; see <ref>.
Furthermore, we also introduce the edges b_iv_i and v_ia_i and set σ(b_iv_i) = σ(v_ia_i) = p_d for all i ∈ [F + 1] .
For every i ∈ [F], we add the edge v_iv_i + 1 and place it on the page p_d, i.e., we have σ(v_iv_i + 1) = p_d as in <ref>.
Finally, we also create the edge b_1a_F + 1 and set σ(b_1a_F + 1) = p_d.
To complete the construction of the fixation gadget, we add the new edges f_iv_i and f_iv_i + 1 for every i ∈ [F] to G.
<ref> shows an example of the fixation gadget for F = 2.


Next, we show that the fixation gadget forces f_i to lie between v_i and v_i + 1 on the spine and the edges f_iv_i and f_iv_i + 1 to be on the page p_d for every i ∈ [F].
lem:fixation-gadget-propertieslemmalemmaFixationGadgetProperties
    
	Let = be an instance of  that contains a fixation gadget on F vertices {f_1, …, f_F}.
	In any solution G to  and for every i ∈ [F], we have v_i ≺ f_i ≺ v_i + 1 and σ(f_iv_i) = σ(f_iv_i + 1) = p_d.
	Furthermore, the fixation gadget contributes 4F + 3 vertices and (ℓ + 4)F + ℓ + 2 edges to the size of .


Towards establishing v_i ≺ f_i ≺ v_i + 1, one can show that f_i≺ v_i would prevent f_i from seeing v_i+1 on any page: As f_i≺ v_i implies f_i ≺ b_i + 1≺ v_i + 1≺ a_i + 1 and we have the edge b_i+1a_i + 1 on any page except p_d, only visibility on page p_d would still be possible.
However, the edges on the page p_d prevent visibility to v_i+1 for any spine position left of v_i.
By symmetric arguments, we can obtain that v_i+1≺ f_i would prevent v_i from seeing f_i. 
Using again the fact that we have the edge b_ia_i on any page except p_d, in concert with the relation v_i ≺ f_i ≺ v_i + 1 shown above and the edges v_ia_i and b_i + 1v_i + 1 on the page p_d, one can deduce that σ(f_iv_i) = σ(f_iv_i + 1) = p_d must hold.
Finally, the bound on the size of the gadget can be obtained by a close analysis of the construction.


plemmaFixationGadgetProperties
	Let G be a solution to =.
	
	
	
	First, we will show that v_i ≺ f_i ≺ v_i + 1 must hold.
	Towards a contradiction, assume that there exists a solution G with f_i ≺ v_i.
	Observe that f_i ≺ v_i also implies f_i ≺ v_i + 1 and recall that we have in H the edges e(b_i + 1, a_i + 1, p) for every page p ≠ p_d.
	As b_i + 1≺_H v_i + 1≺_H a_i + 1 and G is an extension of H, f_i can see v_i + 1 only on the page p_d.
	Hence, we must have σ(f_iv_i + 1) = p_d.
	We will now distinguish between the following two cases.
	On the one hand, there could exist a j with 1 ≤ j < i ≤ F, such that v_j ≺ f_i ≺ v_j + 1≺ v_i + 1.
	However, since we have σ_H(v_jv_j + 1) = p_d, this cannot be the case, as this would introduce a crossing on the page p_d between the edges f_iv_i + 1 and v_jv_j + 1.
	On the other hand, we could have f_i≺ b_1, i.e., f_i is placed at the beginning of the fixation gadget.
	Observe that we have in this situation f_i≺ b_1 ≺ v_i + 1≺ a_F + 1 and σ_H(b_1a_F + 1) = p_d.
	Hence, we would introduce a crossing on the page p_d between the edges f_iv_i + 1 and b_1a_F + 1.
	As σ(f_iv_i + 1) = p_d can therefore not hold, we have no page to which we could assign f_iv_i + 1 without introducing a crossing, contradicting the assumption that we have a solution with f_i≺ v_i.
	As the arguments that exclude v_i + 1≺ f_i are symmetric, we obtain that v_i≺ f_i≺ v_i + 1 must hold in any solution to .
	
	Secondly, we will show that σ(f_iv_i) = σ(f_iv_i + 1) = p_d holds.
	Towards a contradiction, assume that there exists a solution G with σ(f_iv_i) ≠ p_d for some i ∈ [F].
	Hence, σ(f_iv_i) = p holds for some page p ≠ p_d.
	Recall that we have the edge e(b_i, a_i, p) with σ_H(e(b_i, a_i, p)) = p.
	This allows us to strengthen v_i≺ f_i≺ v_i + 1, which we have shown before, to v_i ≺ f_i ≺ a_i under the assumption of σ(f_iv_i) = p, as we would otherwise have a crossing on the page p.
	However, then we can conclude from σ_H(v_ia_i) = p_d and the existence of the edges e(b_i + 1, a_i + 1, p'), with σ_H(e(b_i + 1, a_i + 1, p')) = p', for any page p' ≠ p_d and f_i ≺ b_i + 1≺ v_i + 1≺ a_i + 1 that there does not exist a feasible page assignment for the edge f_iv_i + 1.
	This contradicts our assumption of a solution with σ(f_iv_i) ≠ p_d and a symmetric argument rules out any solution with σ(f_iv_i + 1) ≠ p_d.
	
	Thirdly, we analyze the size of the fixation gadget.
	Recall that ℱ consists of F vertices, and we introduce 3(F + 1) vertices in H.
	Furthermore, the fixation gadget contributes one page to an (existing) stack layout  of H on ℓ - 1 pages.
	Regarding the number of edges, we create in H (ℓ - 1)(F + 1) edges of the form b_ia_i, i ∈ [F + 1], 2(F + 1) edges of the form b_iv_i or v_ia_i, i ∈ [F + 1], F edges of the form v_iv_i + 1, i ∈ [F], and the edge b_1a_F + 1.
	Together with the 2F new edges that we add to G, this sums up to 
	(ℓ + 4)F + ℓ + 2 edges.

<ref> tells us that we can restrict the feasible positions for f_i to a pre-defined set of consecutive intervals by choosing suitable positions for v_i and v_i + 1 in the spine order ≺_H.
As the fixation gadget requires an additional page p_d, we must ensure that the existence of the (otherwise mostly empty) page p_d does not violate the semantics of our reductions. 
In particular, we will (have to) ensure that our full constructions satisfy the following property.

	
	Let = be an instance of  that contains a fixation gadget on F vertices {f_1, …, f_F}.
	In any solution G to  and for every new edge e ∈ with σ(e) = p_d, we have e ∈{f_iv_i, f_iv_i + 1| i ∈ [F]}.




 §.§ The Complete Reduction


long
Recall the base layout of our reduction that we described in <ref> and illustrated with <ref>.
There, we created, for a given formula φ, one vertex for each variable x_i and each clause c_j.
Furthermore, each x_i should only be visible on two pages that correspond to its individual truth state and each c_j should only be visible on three pages that correspond to the complementary literals in c_j.
However, the intended semantics of our reduction rely on the assumption that new vertices can only be placed on a specific position, and in a specific order, on the spine.
Equipped with the fixation gadget, we will now satisfy this assumption.

For an instance φ = (𝒳, 𝒞) of , we take the base layout of our reduction as described in <ref> and incorporate in H a fixation gadget on two vertices, i.e., for F = 2.
We set a_3 ≺ d_1, i.e., we place the fixation gadget at the beginning of the spine, and identify s = f_1 and v = f_2.
Furthermore, we add the edge d_1d_N + M + 1 and set σ(d_1d_N + M + 1) = p_d.
Observe that this ensures that our construction will have <ref>, as this edge prevents connecting s with x_i or v with c_j on page p_d for any i ∈ [N] and j ∈ [M].
Finally, we add to G the new edges sx_i and vc_j for every i ∈ [N] and j ∈ [M].
This completes our reduction and we establish with the following theorem its correctness; see also <ref> for an example of our construction for a small formula.
   




thm:paranp-hardnesstheoremtheoremParaNPHardness
	
	 is -complete even if we have just two new vertices and = ∅.

ptheoremParaNPHardness
    -membership of  follows immediately from the fact that we can encode a solution  in  space and can verify it in polynomial time.
    Thus, we focus in the remainder of the proof on showing -hardness of .

	Let φ = (𝒳, 𝒞) be an instance of  and let = be the obtained instance of .
	The number of vertices and edges in H that we created in the base layout of <ref> is in N + M.
	Furthermore, in the base layout, we used 2N pages.
	Together with the page from the fixation gadget, we have ℓ = 2N + 1.
	As F = 2 is constant, the contribution of the fixation gadget to the size of H and G is linear in φ by <ref>.
	Hence, the overall size of  is polynomial in the size of φ.
	Clearly, the time required to create  is also polynomial in the size of φ and it remains to show the correctness of the reduction.
	
	
	*(⇒)
	Assume that φ is a positive instance of  and let Γ: 𝒳→{0,1} be a truth assignment that satisfies every clause.
	To show that  is a positive instance of , we create a stack layout  of G.
	We first ensure that it extends H by copying H.
	Next, we set a_1 ≺ s ≺ b_2, a_2 ≺ v ≺ b_3 and σ(sv_1) = σ(sv_2) = σ(vv_2) = σ(vv_3) = p_d as shown in <ref>.
	Furthermore, for every variable x_i ∈𝒳, we set σ(sx_i) = p_i if Γ(x_i) = 1 and σ(sx_i) = p_¬ i otherwise.
	For every clause c_j ∈𝒞, we identify a variable x_i that satisfies the clause c_j under Γ.
	As Γ satisfies every clause, the existence of such an x_i is guaranteed.
	Then, we set σ(sx_i) = p_i if Γ(x_i) = 0 and σ(sx_i) = p_¬ i otherwise.
	
	To show that  is crossing-free, we first observe that for the fixation gadget, our generated solution satisfies the necessary properties stated in <ref>.
	We can observe that in our page assignment new edges cannot cross old edges.
	Hence, we only have to ensure that no two new edges cross.
	No two new edges on page p_d can cross, so assume that there is a crossing on page p_i for some i ∈ [N].
	We observe that only edges of the form sx_i and vc_j for some x_i ∈𝒳 and c_j ∈𝒞 can cross, as they are otherwise incident to the same vertex.
	As there is a crossing on the page p_i, we must have by construction that the variable x_i appears negated in the clause c_j but we have Γ(x_i) = 1.
	Hence, x_i does not satisfy c_j, which is a contradiction to our construction of , for which we only considered variables that satisfy the clause c_j.
	Therefore, a crossing on the page p_i cannot exist.
	As the argument for a crossing on page p_¬ i is symmetric, we conclude that  must be crossing-free and hence witnesses that  is a positive instance of .
		 
	*(⇐)
	Assume that  is a positive instance of .
	This implies that there exists a witness extension G of H.
	As  contains the fixation gadget, we can apply <ref> and deduce that s ≺ v ≺ d_1 holds.
	Based on G, we now construct a truth assignment Γ𝒳→{0,1} for φ.
	For each variable x_i ∈𝒳, we consider the page assignment σ(sx_i).
	Recall that we have s ≺ d_1 ≺ x_i ≺ d_N + M + 1 and σ_H(d_1d_N + M + 1) = p_d.

	Together with s ≺ d_i ≺ x_i ≺ d_i + 1 and σ_H(d_id_i + 1) = p for any page p ∈[ℓ] ∖{p_d, p_i, p_¬ i}, we conclude that σ(sx_i) ∈{p_i, p_¬ i} must hold.
    We set Γ(x_i) = 1 if σ(sx_i) = p_i holds and Γ(x_i) = 0 if σ(sx_i) = p_¬ i holds and know by the above arguments that Γ is well-defined.
	What remains to show is that Γ satisfies φ.
	Let c_j be an arbitrary clause of φ and consider the page p with σ(vc_j) = p.
	As we have σ_H(d_1d_N + M + 1) = p_d we know that p ≠ p_d must hold, i.e., the page p is associated to some variable x_i.
	For the remainder of the proof, we assume p = p_i as the case p = p_¬ i is symmetric.
	Recall that we have d_N + j≺_H c_j ≺_H d_N + j + 1, σ_H(e(c_j, p_i')) = p_i', and σ_H(e(c_j, p_¬ i')) = p_¬ i' for any variable x_i'∈𝒳 that does not occur in c_j.
	Hence, we know that x_i must occur in c_j.
	Furthermore, the same reasoning allows us to conclude that x_i must appear negated in c_j, as we would otherwise have a crossing.
	Using s ≺ v ≺ x_i ≺ c_j and our assumption of σ(vc_j) = p_i, we derive that x_i will be visible from s on page p_¬ i only, i.e., we have σ(sx_i) = p_¬ i.
	By our construction of Γ, we conclude Γ(x_i) = 0.
	Hence, x_i satisfies c_j under Γ.
	As c_j was selected arbitrarily, this holds for all clauses and therefore must Γ satisfy the whole formula φ, i.e., it witnesses that φ is a positive instance of .

long
Finally, we want to remark that <ref> is tight in the sense that with only one new vertex v and = ∅ can be solved in polynomial time.
To that end, we can branch over all n possible spine positions where v can be placed.
For each of these, the observation that edges incident to the same vertex can never cross each other allows us to greedily assign a new edge uv to the first page p where v can see u.
Recall that we only add one new vertex v.
Hence, u is an old vertex whose spine position is known.
Clearly, an extension exists if and only if there exists a spine position for v such that our greedy page assignment can find a page for all new edges.

    
    Let = be an instance of  with = 1 and = ∅.
	We can find an ℓ-page stack layout of G that extends  or report that none exists in n ·· time.
    













§  PARAMETERIZED BY MISSING VERTICES AND EDGES IS IN 


In the light of <ref>, which excludes the use of the vertex+edge deletion distance as a pathway to tractability, we consider parameterizing by the total number of missing vertices and edges κ+. 
As our first result in this direction, we show that 
parameterizing  by κ makes it -tractable.





To this end, 
we combine a branching-procedure with the 
fixed parameter algorithm for the special case obtained in <ref>.








	
	Let = be an instance of .
	We can find 
    an ℓ-page stack layout of G that extends  or report that none exists in ^+ 1^ time.



	We branch over the possible assignments of new vertices to the intervals in ≺_H.
	As a solution could assign multiple vertices to the same interval, 
    we also branch over the order in which all vertices will appear in the spine order ≺_G.
	Observe that ≺_H induces V(H) + 1 different intervals, out of which we have to choose  with repetition.
	Together with the possible orders of the new vertices, we can bound the number of branches by !·V(H) +. 
	
    We can simplify this expression to
    
    !· (V(H) + )!/!· ((V(H) + ) - )! = (V(H) + )!/V(H)! = Π_i = 1^(V(H) + i) = ^.

	
	In each branch, the spine order ≺_G is fixed and extends ≺_H.
	Hence, it only remains to check whether ≺_G allows for a valid page assignment σ_G.
	
	
    As each branch corresponds to an instance 
    of  where only edges are missing,
	
	
    we use <ref> to check in ^· time whether such an assignment σ_G exists.
    The overall running time now follows readily.
    

The running time stated in <ref> not only proves that  is in  when parameterized by κ, but also  when parameterized by  for constant .
However, common complexity assumptions rule out an efficient algorithm parameterized by κ, as we show next.




§  PARAMETERIZED BY MISSING VERTICES AND EDGES IS [1]-HARD






In this section, we show that  parameterized by the number κ of missing vertices and edges is [1]-hard.
To show [1]-hardness, we reduce from the Multi-colored Clique () problem.
Here, we are given a graph G_C, an integer k > 0, and a partition of V(G_C) into k independent subsets V_1, …, V_k, and ask whether there exists a colorful k-clique 𝒞⊆ V(G_C) in G_C, i.e., a clique on k vertices that contains exactly one vertex of every set V_i, i ∈ [k].
It is known that  is [1]-hard when parameterized by k <cit.>.
In the following, we will use Greek letters for the indices of the partition and denote with n_α the number of vertices in V_α, i.e., n_α = V_α.
Observe that ∑_α∈ [k] n_α = N with N = V(G_C).
As we can interpret the partitioning of the vertices into V_1, …, V_k as assigning to them one of k colors, we will call a vertex v_α^i 
with α∈ [k] and i ∈ [n_α] a vertex with color α.
Our construction will heavily use the notion of a successor and predecessor of a vertex in a given spine order ≺.
For a vertex u, the function ≺u returns the successor of u in the spine order ≺, 
i.e., the consecutive vertex in ≺ after u.
Note that ≺u is undefined if there is no  vertex v ∈ V(G) with u ≺ v.
We write u if ≺ is clear from context.
The predecessor function ≺u is defined analogously.
mccIntro

    Let (G_C, k, (V_1, …, V_k)) be an instance of .
    We will construct an  instance  parameterized by κ that will fulfill two crucial properties to ensure its correctness.
	While, at the time of stating the property, our construction might not yet fulfill it, we show in <ref> that in the end it indeed has the desired properties.

long
Our instance contains for every original vertex v_α^i ∈ V(G_C) a copy u_α^i ∈ V(H).
Furthermore, we add for each color α∈ [k] to H two additional vertices and, overall, three further dummy vertices that we use to ensure correctness of the reduction.
We place the vertices on the spine based on their color α and index i; see <ref> and <ref>, where we give the full details of the base layout.
Observe that every vertex v_α^i ∈ V(G_C) induces the interval [u_α^i, u_α^i + 1] in ≺_H, which we denote with v_α^i.
The equivalence between the two problems will be obtained by adding a k-clique to G that consists of the k new vertices 𝒳 = {x_1, …, x_k}.
Placing x_α∈𝒳 in v_β^i indicates that v_β^i will be part of the colorful k-clique in G_C.



To establish the correctness of our reduction, we have to ensure two things.
First, we have to model the adjacencies in G_C.
In particular, two new vertices x_α and x_β, with α < β, should only be placed in intervals induced by vertices adjacent in G_C.
We enforce this by adding for every edge e = v_α^iv_β^j ∈ E(G_C) a page p_e that contains a set of edges creating a tunnel on p_e, see <ref>, and thereby allowing us to place the edge x_αx_β∈ E(G) in the page p_e if and only if x_α is placed in v_α^i and x_β in v_β^j. 
Hence, the page assignment verifies that only pairwise adjacent vertices are in 
the solution, i.e., new vertices can only be placed in intervals induced by a clique in G_C.
We 
describe the tunnel further in <ref>.

Second, we have to ensure that we select exactly one vertex v_α^i ∈ V_α for every color α∈ [k].
In particular, the new vertex x_α should only be placed in intervals that are induced by vertices from V_α.
To this end, we modify H to include an appropriate fixation gadget by 
re-using some vertices of the base layout; see <ref> for details.
As the whole base layout thereby forms the fixation gadget, our construction trivially satisfies <ref>.

The above two ideas are formalized in <ref>.


With these properties at hand, we show at the end of <ref> that  is [1]-hard when parameterized by κ.

As in the reduction from <ref>, we will allow multi-edges in the graph H to facilitate presentation and understanding.
In <ref> we will discuss a way to remove the multi-edges by distributing the individual edges over auxiliary vertices.


In the following, we first give an overview of and intuition behind our reduction in <ref>, before we show its correctness in <ref>.
Note that the full details of the construction can be found in <ref>.
Furthermore, as in the reduction from <ref>, we will allow multi-edges in the graph H to facilitate the presentation of the reduction. The procedure for removing multi-edges by distributing the individual edges over auxiliary vertices is detailed in <ref>.



 §.§ An Overview of the Construction




First, we define the base layout of our reduction, see <ref> for full details.
In the base layout, we create the N + 2k + 3 vertices {u_α^j |α∈ [k], j ∈ [n_α + 1]_0}∪{u_0^0, u_^0, u_^1} in H.
Note that for each original vertex v_α^i ∈ V(G_C), we have a copy u_α^i.
We will refer to the vertices u_0^0, u_^0, and u_^1 as dummy vertices and set, for ease of notation, = k + 1 and n_ = 1.
The vertices are placed on the spine based on their color α and index i; see <ref>.
Finally, observe that u_α^i =  u_α^i + 1 for every v_α^i ∈ V(G_C).
Furthermore, every vertex v_α^i ∈ V(G_C) induces the interval [u_α^i, u_α^i + 1] in ≺_H, which we denote with v_α^i.
The equivalence between the two problems will be obtained by adding a k-clique to G that consists of the k new vertices 𝒳 = {x_1, …, x_k}.
Placing x_α∈𝒳 in v_β^i indicates that v_β^i will be part of the colorful k-clique in G_C, i.e., we will have the equivalence u_α^i ≺ x_α≺ ≺_Hu_α^i p. d.⟺ x_α is placed in v_α^i ⟺ v_α^i ∈𝒞 between a solution G to  and a solution 𝒞 to .
To guarantee that 𝒞 is colorful, i.e., contains exactly one vertex from each color, we will ensure the following property with our construction.








	
	
	
	





























To establish the correctness of our reduction, we have to ensure two things.
First, we have to model the adjacencies in G_C.
In particular, two new vertices x_α and x_β, with α < β, should only be placed in intervals induced by vertices adjacent in G_C.
We enforce this by adding for every edge e = v_α^iv_β^j ∈ E(G_C) a page p_e.
On this page p_e, we create the following edges in H; see also <ref> for a visualization.
Firstly, we create for every color γ∈ [k] ∖{α, β} an edge that spans exactly the intervals induced by vertices of color γ, thereby intuitively blocking visibility to any interval induced by a vertex of a color different to α and β; see <ref>a.
Secondly, we create up to two edges that span all intervals induced by vertices of color α except v_α^i; see <ref>b.
We do so similarly for color β.
These edges in concert with a tunnel that we create on page p_e, see <ref>c and <ref> for a formal description, allow us to place the edge x_αx_β∈ E(G) in the page p_e if and only if x_α is placed in v_α^i and x_β in v_β^j.
More formally, our construction will ensure the following property.














Second, we have to ensure that we select exactly one vertex v_α^i ∈ V_α for every color α∈ [k].
In particular, the new vertex x_α should only be placed in intervals that are induced by vertices from V_α.
To this end, we modify H to include a fixation gadget on F = k vertices by 
re-using some vertices of the base layout.
Most importantly, we identify v_α = u_α^0 for every α∈[k + 1] and f_α = x_α for every α∈[k]; see <ref> for details.
As the whole base layout thereby forms the fixation gadget, our construction trivially satisfies <ref>.




long
    Throughout the description of the reduction, we explicitly highlight crucial places where our construction should fulfill certain properties to ensure its correctness.
    While, at the time of stating the property, our construction might not yet fulfill it, we argue in <ref>long (and <ref>) that it in the end indeed has the desired properties.
    With these properties at hand, we show at the end of <ref> that  is [1]-hard when parameterized by κ.




















































sectionWOneBaseLayout
	

 §.§ Creating Intervals on the Spine: Our Base Layout

	
	
	
	
	
	
	
	
	long
	
	Recall that G_C has the vertex set V(G_C) = {v_1^1, …, v_k^n_k} partitioned into V_1, …, V_k with V_α = {v_α^1, …, v_α^n_α} for α∈ [k].
	We create the N + 2k + 3 vertices {u_α^j |α∈ [k], j ∈ [n_α + 1]_0}∪{u_0^0, u_^0, u_^1} in H.
	Note that for each original vertex v_α^i ∈ V(G_C), we have a copy u_α^i.
	We will refer to the vertices u_0^0, u_^0, and u_^1 as dummy vertices and set, for ease of notation, = k + 1 and n_ = 1.
	We order the vertices of H on the spine by setting u_α^i ≺ u_α^i + 1 and u_α^n_α + 1≺ u_α+1^0 for every α∈ [k] and i ∈ [n_α]_0.
	Furthermore, we set u_0^0 ≺ u_1^0 and u_^0 ≺ u_^1.
	The spine order is then the transitive closure of the above partial orders.
	We visualize it in <ref> and observe that u_α^i =  u_α^i + 1 for every v_α^i ∈ V(G_C).
	
	
	
	
		
		
		
		
	
	
	
	As already indicated, we define the set 𝒳 = {x_1, …, x_k} to contain k (new) vertices which we add to G.
	Furthermore, we form a k-clique on 𝒳, i.e., we add the edges x_αx_β for 1 ≤α < β≤ k to E(G).
	Recall that v_α^i denotes the interval [u_α^i, ≺_Hu_α^i].
	We use the following equivalence between a solution G to  and a solution 𝒞 to .
	
    u_α^i ≺ x_α≺≺_Hu_α^i p. d.⟺ x_α is placed in v_α^i ⟺ v_α^i ∈𝒞

	To guarantee that 𝒞 is colorful, i.e., contains exactly one vertex from each color, we will ensure the following property with our construction.
	long*
	longOf course, our construction does not yet fulfill <ref>.
	We will show in <ref> that the finished construction indeed does fulfill <ref>.
	


sectionWOneEdges


 §.§ Creating One Page Per Edge: Encoding the Adjacencies


Having fixed the base order on the spine, we now ensure that we only select vertices that are adjacent in G_C, i.e., we encode the edges of G_C in our stack layout H.
Let e = v_α^iv_β^j be an edge of G_C and recall that, by our assumption, we have α≠β.
Furthermore, we assume for ease of presentation that α < β holds, which implies u_α^i≺ u_β^j.
We create the following edges in H; see <ref>.
Note that each of the them is assigned to the page p_e in σ, where p_e is a new empty page that we associate with the edge e.
Firstly, we create the edge u_γ^1u_γ^n_γ + 1 for each γ∈ [k] ∖{α, β}; see <ref>a.
Secondly, we create the edges u_α^1u_α^i and u_α^i + 1u_α^n_α + 1 as shown in <ref>b.
Similarly, we add the edges u_β^1u_β^j and u_β^j + 1u_β^n_β + 1.
If i ∈{1, n_α} or j ∈{1, n_β}, we omit creating the respective edge to not introduce self-loops in H.
Thirdly, we create the edges u_α^iu_β^j + 1 and u_α^i + 1u_β^j, which we mark in <ref>c in black.
long
One can readily verify that these edges in the page p_e do not cross.
Furthermore, observe that the edges u_α^iu_β^j + 1 and u_α^i + 1u_β^j create a tunnel on the page p_e connecting v_α^i and v_β^j.
Intuitively, the edges on the page p_e ensure that if x_i is placed in v_α^i then x_i sees only v_β^j on page p_e.
More formally, we will have the following property.
long*







sectionWOneFixationGadget


 §.§ Restricting The Placement of New Vertices: Encoding the Colors


Until now, the new vertices in 𝒳 can be placed in any interval on the spine.
However, in  we must select exactly one vertex from each color.
Recall <ref>, which intuitively states that each new vertex should only be placed in intervals that correspond to its color.
We now use the fixation gadget to ensure that our construction fulfills <ref>.
Observe that we already introduced in <ref> the required vertices of the fixation gadget when creating the base layout of our reduction.
More specifically, we (implicitly) create in H and our construction the fixation gadget on F = k vertices ℱ = 𝒳 by identifying, for α∈ [k + 1], v_i = u_α^0, b_i = u_α^0, and a_i = u_α^0, where we use i = α to differentiate between the vertices from the fixation gadget and the graphs G_C and H.
We also introduce the corresponding edges of the fixation gadget, which we visualize for the vertices in this construction in <ref>.

Recall that when introducing the fixation gadget in <ref>, we required that our instance must fulfill <ref>, which states that p_d must only be used by new edges that were introduced in the fixation gadget.
However, observe that any new edge e ∈ E(G) ∖ (E(H) ∪{x_αu_α^0, x_αu_α + 1^0 |α∈ [k]}), i.e., that was not introduced in the fixation gadget, is of the form e = x_αx_β for 1 ≤α < β≤ k, i.e., one of the edges in the k-clique.
<ref> tells us that for every new vertex x_α∈𝒳 we have u_α^0 ≺ x_α≺ u_α + 1^0 in any extension G of H.
This implies that we have u_α^0 ≺ x_α≺ u_α + 1^0 ≼ u_β^0 ≺ x_β≺ u_β + 1^0.
Together with having u_α^0u_α + 1^0, u_β^0u_β + 1^0 ∈ E(H) and σ_H(u_α^0u_α + 1^0) = σ(u_β^0u_β + 1^0) = p_d, this rules out σ_G(x_αx_β) = p_d.
Hence, we observe that the fixation gadget is formed on the base layout and our construction thus (trivially) fulfills <ref>.













 §.§ Bringing It Together: Showing Correctness of the Reduction


long
We start by shortly summarizing our construction.
Recall that we want to insert k new vertices that form a clique.
On a high level, we first created for each vertex v_α^i ∈ V(G_C) a copy u_α^i ∈ V(H) and ordered the latter vertices depending on the color α and the index i.
Then, we created for each edge e ∈ E(G_C) a page p_e on which we formed a tunnel that will enforce for every new edge assigned to p_e that its endpoints lie in specific intervals via <ref>.
Finally, we used the fixation gadget to ensure that a new vertex can only be placed in intervals for its color, i.e., that our construction will enforce <ref>.
Overall, we obtain for an instance (G_C, k, (V_1, …, V_k)) of  an instance = of  that we parameterize by the number κ of missing vertices and edges.
Before we show correctness of the reduction, we first argue in <ref> that  fulfills <ref>, respectively.

With the overview of the construction and the intuition behind the reduction settled, we now proceed to show its correctness in <ref>.
In the proof, we make use of <ref>.
Therefore, on our path to obtain <ref>,



we first have to show that our construction fulfills them.







Recall that <ref> is defined as follows.
*
longIn <ref>, whenWhen
incorporating the fixation gadget on F = k vertices in our construction, we identified
long
v_i = u_α^0 and f_i = x_α for every α∈ [k] and i = α.
v_α = u_α^0 and f_α = x_α for every α∈ [k].
Similarly, we identified v_F + 1 = u_k + 1^0.
The fixation gadget now guarantees thanks to <ref> that we have v_α≺_G f_α≺_G v_α + 1, i.e., u_α^0 ≺ x_α≺ u_α + 1^0, in any solution G.
Hence, we can observe the following.

	
	Our instance  of  fulfills <ref>.















































Recall that <ref> furthermore tells us that we have in any solution G the page assignment σ(x_αu_α^0) = σ(x_αu_α + 1^0) = p_d for every α∈ [k].
As we have by <ref> u_α^0 ≺ x_α≺ u_α + 1^0 and furthermore by the construction of the fixation gadget

	σ_H(u_α^0u_α^0) = σ_H(u_α^0u_α^0) = p_d

for every α∈ [k], we cannot have in G u_α^0 ≺ x_α≺≺_Hu_α^0 or ≺_Hu_α + 1^0≺ x_α≺ u_α + 1^0, as this would introduce a crossing on page p_d.








As we have in ≺_H the equality u_α^0 = u_α^1 and u_α + 1^0 = u_α^n_α + 1 for every α∈ [k], we can strengthen <ref> and obtain the following.

	
 In a solution  to  we have u_α^1 ≺ x_α≺ u_α^n_α + 1 for every α∈ [k].






Finally, we now show that our construction fulfills <ref>, which was defined as follows.

*

lemmalemmaWOneFulfillsPropertyLayers
	
	Our instance  of  fulfills <ref>.


	First, recall that we made <ref>, i.e., our construction fulfills <ref>.
	Let G be a solution to  with σ(x_αx_β) = p_e, for e = v_α^iv_β^j∈ E(G_C), 1 ≤α < β≤ k.
	<ref> tells us that u_α^1 ≺ x_α≺ u_α^n_α + 1 and u_β^1 ≺ x_β≺ u_β^n_β + 1 holds.
	<ref> also holds for any new vertices x_γ and x_δ with γ, δ∈ [k] ∖{α, β} and γ≠δ.
	Furthermore, we have the edges u_γ^1u_γ^n_γ + 1 and u_δ^1u_δ^n_δ + 1 on page p_e.
 Hence, all new edges on page p_e must be among new vertices placed in intervals induced by vertices of color α or β. 
	
	Now assume that we have u_α^1 ≼ x_α≼ u_α^i.
	Using σ_H(u_α^1u_α^i) = p_e together with u_α^1 ≼ x_α≼ u_α^i ≺ x_β, we derive that u_α^1 ≼ x_α≼ u_α^i results in a crossing on page p_e.
	Hence, u_α^1 ≼ x_α≼ u_α^i cannot hold.
	Now assume that we have u_α^i + 1≼ x_α≼ u_α^n_α + 1.
	From σ_H(u_α^i + 1u_α^n_α + 1) = p_e and u_α^i + 1≼ x_α≼ u_α^n_α + 1≺ x_β we get that u_α^i + 1≼ x_α≼ u_α^n_α + 1 results in a crossing on page p_e.
	Hence, u_α^i + 1≼ x_α≼ u_α^n_α + 1 cannot hold.
	Since we can exclude u_α^1 ≼ x_α≼ u_α^i and u_α^i + 1≼ x_α≺ u_α^n_α + 1 by the construction of the tunnel on page p_e, we can derive that x_α must be placed in v_α^i.
	As similar arguments can be made for x_β, we can conclude that we get a crossing on page p_e unless x_α is placed in v_α^i and x_β in v_β^i.


long
We are now ready to show correctness of our reduction, i.e., show the following theorem.
thm:w-1theoremtheoremWOne
	
	 parameterized by the number κ of missing vertices and edges is -hard.


Let (G_C, k, (V_1, …, V_k)) be an instance of  with N = V(G_C) and M = E(G_C) and let = be the instance of  parameterized by the number κ of missing vertices and edges created by our construction described above. Closer analysis 
reveals that the size of  is bounded by N + Mk + k^2, and we have κ = 3k + k2 as = k and = k2 + 2k; recall that the fixation gadget contributes 2k new edges.

Towards arguing correctness, assume that (G_C, k, (V_1, …, V_k)) contains a colorful k-clique 𝒞. We construct a solution to  by, for every new vertex x_α∈𝒳, considering the vertex v_α^i ∈𝒞 and placing x_α immediately to the right of the copy u_α^i of v_α^i in H. The fact that 𝒞 is a clique then guarantees that, for each edge e∈ E(G_C[𝒞]), there exists the page p_e in which the corresponding edge e' ∈ E(G[𝒳]) can be placed in. For the remaining edges from the fixation gadget, we can use the page assignment from <ref>.

For the converse (and more involved) direction, assume that  admits a solution G. By <ref>, we have that each x_α∈ must be placed between u_α^0 and u_α + 1^0. 
Moreover, our construction together with the page assignment forced by <ref> guarantees that x_α is placed between precisely one pair of consecutive vertices u_α^i_α and u_α^i_α+1, for some i_α∈ [n_α]; recall <ref>.
Our solution 𝒞 to the instance of  will consist of the vertices v_α^i_α, i.e., exactly one vertex per color α.
Moreover, each new edge x_α x_β∈ E(G[𝒳]) must be placed by σ_G on some page, and as our construction satisfies <ref>, this page must be one that is associated to one edge e = v_α^i_αv_β^i_β of G_C. 

<ref> now also guarantees that this page assignment enforces that x_α and x_β are placed precisely between the consecutive vertices u_α^i_α and u_α^i_α+1 and u_β^i_β and u_β^i_β+1 of H, respectively.
This means that the vertices in 𝒞 are pairwise adjacent, which implies that 𝒞 is a colorful k-clique.

ptheoremWOne
	Let (G_C, k, (V_1, …, V_k)) be an instance of  with N = V(G_C) and M = E(G_C).
	Furthermore, let = be the instance of  parameterized by the number κ of missing vertices and edges created by our construction described above.
	
	We first bound the size of  and note that we create N + 2k + 3 vertices in H in <ref> and k additional new vertices in G in <ref>.
	We enrich H by k + 4 edges for each edge e ∈ E(G_C).
	This gives us M(k + 4) edges in H so far.
	Furthermore, in <ref>, we use a fixation gadget to keep the new vertices in place.
	As we introduce for the fixation gadget no new vertex but rather identify vertices of the fixation gadget with already introduced ones from H, it only remains to account for the edges of the gadget, which are (M + 5)k + M + 3; see <ref> and note that H has ℓ = M + 1 pages as we create one page for each edge in G_C and have the dummy page from the fixation gadget.
	Finally, we also add a clique among the k new vertices, which are k2 additional edges.
	Overall, the size of H and G is therefore in N + Mk + k^2.
	Hence, the size of the constructed instance is polynomial in the size of G_C and the new parameters are bounded by a (computable) function of the old parameter, more specifically, we have = k and = k2 + 2k, thus κ = 3k + k2. 
	The instance  can trivially be created in (κ)-time.
	We conclude with showing the correctness of our construction.
	
	*(⇒)
	Let (G_C, k, (V_1, …, V_k)) be a positive instance of  with solution 𝒞 = {v_1^i, …, v_k^j}.
	We construct a witness extension G of H to show that  is a positive instance of .
	First, we copy H to ensure that 



	G extends H.
        Then, we extend G as follows.
	
	For every v_α^i∈ 𝒞, we set u_α^i≺ x_α≺ u_α^i + 1.
	We also set σ(x_αu_α^0) = σ(x_αu_α + 1^0) = p_d.
	For every x_α, x_β∈𝒳 with 1 ≤α < β≤ k let x_α be placed in v_α^i and x_β be placed in v_β^j.
	We set σ(x_αx_β) = p_e for the edge e = v_α^iv_β^j.
	As 𝒞 is a clique, we must have v_α^iv_β^j∈ E(G_C) and thus we have the page p_e in , i.e., this page assignment is well-defined.
	This completes the creation of G.
	As it is an extension of H by construction, we only show that no two edges on the same page cross.
	
	It is trivial that no two new edges, i.e., edges from  can cross as they are all put on different pages.
	For the edges x_αu_α^0 and x_αu_α + 1^0 it is sufficient to observe that we assemble the necessary page assignment from <ref>.
	
	What remains to do is to analyze edges of the form x_αx_β.
	Recall that we set σ(x_αx_β) = p_e for e = v_α^iv_β^j and x_α is placed in v_α^i and x_β is placed in v_β^j.
	To see that there does not exist an old edge e' = uv ∈ E(H) that crosses e, i.e., with σ(e') = p_e and u ≺ x_α≺ v ≺ x_β, recall that the only old edge e' = uv on the page p_e for which we have u ≺ x_α≺ v is the edge e' = u_α^iu_β^j + 1 but we have x_β≺ u_β^j + 1, i.e., the edge e' “spans over” the edge x_αx_β.
	As a similar argument can be made to show that there cannot exist an edge e' = u v ∈ E(H) with σ(e') = p_e and x_α≺ u ≺ x_β≺ v, we conclude that there are no crossings on the page p_e.
	
	As all edges are covered by these cases, we conclude that no two edges of the same page in G can cross, i.e., G is a witness that  is a positive instance of . 
	
	*(⇐)
	Let  be a positive instance of .
	Hence, their exists a stack layout G that extends H.
	We now construct, based on G, a set 𝒞 of k vertices and show that it forms a colorful clique in G_C.
	Recall that  fulfills <ref> and contains the fixation gadget.
	From <ref> and <ref>, we conclude that we have u_α^1 ≺ x_α≺ u_α^n_α + 1 for each α∈ [k].
	Let x_α be placed in some v_α^i.
	We now employ our intended semantics and add v_α^i to 𝒞.
	<ref> ensures that each vertex in 𝒞 will have a different color, i.e., for each α∈ [k] there exists exactly one vertex v_α^i ∈𝒞 such that v_α^i ∈ V_α.
	Hence, it remains to show that 𝒞 forms a clique in G_C.
	
	Let x_α, x_β∈ be two arbitrary new vertices placed in v_α^i and v_β^j, respectively.
	Assume without loss of generality x_α≺ x_β.
	To show v_α^iv_β^j∈ E(G_C) let us consider the edge x_αx_β∈ E(G).
	We have σ(x_αx_β) = p for some page p ∈ [ℓ].
	Trivially, p ≠ p_d because u_α^0 ≺ x_α≺ u_α + 1^0 ≺ x_β and σ_H(u_α^0u_α + 1^0) = p_d.
	Furthermore, for any e  = uv ∈ E(G_C) with u ∉V_α and v ≠ V_α we get p ≠ p_e.
	This follows from σ_H(u_α^1u_α^n_α + 1) = p_e and u_α^1 ≺ x_α≺  u_α^n_α + 1≺ x_β.
	Similar arguments also hold if u ∉V_β and v ∉V_β.
	Hence, p = p_e for an edge e ∈ E(G_C) ∩ (V_α× V_β) must hold.
	However, now all prerequisites for <ref> are fulfilled.
	Thus, we can conclude that the only possible edge e is e = v_α^iv_β^j.
	For any other edge e' ∈ E(G_C) ∩ (V_α× V_β) either x_α or x_β are not positioned in the right interval with respect to ≺_G.
    Thus, <ref> tells us (indirectly) that we cannot use this page for the edge x_αx_β.
	As the edge x_αx_β has to be placed in some page, and we ruled out every possibility but the page that would be created for the edge v_α^iv_β^j, we conclude that v_α^iv_β^j∈ E(G_C) must hold.
	As x_α and x_β were two arbitrary new vertices from , we derive that 𝒞 forms a (colorful) clique in G_C, i.e., (G_C, k, (V_1, …, V_k)) is a positive instance of .


<ref> shows an example of the reduction for a small graph G_C with three colors.
long
    Taking a closer look at our construction for <ref> (and <ref>), we make the following observation.
    Consider a line l perpendicular to the spine.
    On the page p_e for an edge e = v_α^iv_β^j ∈ E(G_C), the line l intersects at most one edge if placed in the interval for a color γ with γ < α or γ > β.
    If α < γ < β, the line l can in addition intersect the edges u_α^iu_β^j + 1 and u_α^i + 1u_β^j of <ref>c.
    Finally, if γ∈{α, β}, the line l intersects at most the full span of the tunnel, which has a width of three, see again <ref>.
    Hence, the width of the page p_e is at most three.
    Similarly, for the page p_d, <ref> show that its width is also at most three. Hence, the page width ω of H is constant and we obtain <ref>.

Since in a stack layout constructed by our reduction each line perpendicular to the spine intersects a constant number of edges, see also <ref>, we also obtain:



    
     parameterized by the number κ of missing vertices and edges and the page width ω of the given layout, i.e., by κ + ω, is -hard.







































































































































































































































































































































	


































	










	









	







	







	

	










	














































§ ADDING THE NUMBER OF PAGES AS PARAMETER FOR 




In this section, we complete the landscape of <ref> by showing that becomes fixed-parameter tractable once we add ℓ to the parameterization considered by <ref>long, i.e., we show the following theorem.
.


We will make use of the following concepts.








long


Consider a page p of a stack layout  of G and recall that we can interpret it as a plane drawing of the graph G' with V(G') = V(G) and E(G') = {e ∈ E(G) |σ(e) = p} on a half-plane, where the edges are drawn as (circular) arcs.
A face on the page p in  coincides with the notion of a face in the drawing (on the half-plane p) of G'.
This also includes the definition of the outer-face.
See <ref> for a visualization of longthese and the following conceptsthis concept and observe that we can identify every face, except the outer-face, by the unique edge e = uv ∈ E(G) with u ≺ v and σ(e) = p that bounds it from upwards.

long
In the following, we will address a face by the edge it is identified with.
Similarly, we say that an edge induces the face it identifies.
We say that a vertex w is incident to the face uv (on some page p) if u ≼ w ≼ v holds and there does not exist a different face u'v' (on the page p) with u ≼ u' ≼ w ≼ v' ≼ v.
Similarly, an interval [w, x] is incident to a face if w and x are incident to the face.
Finally, we say that a face uv spans an interval [w, x] if u ≼ w ≺ x ≼ v holds; note that [w, x] might not be incident to the face uv.

Let ⊆ V(H) be the vertices of H that are incident to new edges, i.e., {u ∈ V(H) |there is an edge e = uv ∈}.
The size of  is upper-bounded by 2. 

We will define an equivalence class on the intervals of ≺_H based on the location of the vertices from .
Consider the two intervals [u_1, v_1] and [u_2, v_2] defined by the old vertices u_1, v_1, u_2 and v_2, respectively.
These two intervals are in the same equivalence class if and only if 
{w ∈| w ≼ u_1} = {w ∈| w ≼ u_2} and {w ∈| v_1 ≼ w} = {w ∈| v_2 ≼ w }
holds.

Each equivalence class, which we call , consists of a set of consecutive intervals delimited by (up to) two old vertices; see <ref>.
Note that the first and last  are defined by a single vertex v ∈.
The number of  is bounded by 2 + 1.
notationSuperInterval
    We denote the  delimited by the two vertices u, v ∈ with u ≺ v by [[u, v]]. 
    For the remainder of this paper, we assume that every  is bounded by two vertices.
    This is without loss of generality, since we can place dummy vertices at the beginning and end of the spine and assume that they bound the first and the last interval.
    Furthermore, we write w = [[u, v]] to denote that the new vertex w ∈ is placed, with respect to a given spine order ≺_G, in the  [[u, v]].

Furthermore, for a given ≺_G, we define  to be its restriction to new vertices, i.e., for every two vertices u, v ∈ we have that u ≺ v implies u  v.
long
    

    A Helpful Lemma Towards the Fixed-Parameter Algorithm.

    
    

    The Algorithm.


With the above concepts at hand, we can now describe our algorithm.
It consists of a branching step, where we consider all possible page assignments for the new edges, all relative orders among the new vertices, all their possible assignment to , and all distances new edges can have from the outer-face.
long
    The core of our algorithm is a (dynamic programming) algorithm that we apply in each branch.
    In particular, we aim to show the following lemma.

    In the following, we show that we can verify in polynomial-time whether a branch can be extended to a solution  or not.
    The core of our algorithm is a dynamic program that we apply in each branch.
lem:dplemmalemmaDP
	
    Given an instance = of ,
 a page assignment σ_G for all edges,
 an order  in which the new vertices will appear along the spine,
 for every new vertex v ∈ an assignment to a , and
 for every new edge e an assigned distance ω_e to the outer face with respect to H and .
    In 
    
    ··
     time we can compute an ℓ-page stack layout of G that extends  and respects the given assignments – or report that no such layout exists.


    We first observe that assignments (i)–(iv) fix everything except for the actual position of the new vertices within their .
    Especially, assignment (i) allows us to check whether an edge e∈ incident to two old vertices crosses any old edge or another new edge from .
    Furthermore, assignments (i) and (ii) allow us to check whether two new edges e = ua, e' = vb ∈ with u,a,v,b∈ will cross. 
 
    Adding assignment (iii), we can also check this for new edges with some endpoints in V(H), i.e., extend this to all u,a,v,b∈ V(G).
    If the assignments imply a crossing or contradict each other, we can directly return that no desired layout exists.
    
    These checks can be performed in 
    ^2 + · time.
    It remains to check whether there exists a stack layout in which no edge of ∖ intersects an old edge.
    This depends on the exact intervals new vertices are placed in.
    
    To do so, we need to assign new vertices to faces such that adjacent new vertices are in the exact same face and not two different faces with the same distance to the outer face.
    
    We will find this assignment using a dynamic program that models whether there is a solution that places the first j new vertices (according to ) within the first i intervals in ≺_H.
    When placing vertex v_j + 1 in the ith interval, we check that all preceding neighbors are visible in the faces assigned by (iv).
    When advancing to the interval i + 1, we observe that when we leave a face, all edges with the same or a higher distance to the outer face need to have both endpoints placed or none.
    We thus ensure that for no edge only one endpoint has been placed; see also <ref>.
    These checks require  time for each of the ·V(H) combinations of j and i.
    Once we reach the interval V(H) + 1 and have successfully placed all  new vertices, we know that there exists an ℓ-page stack layout of G that extends  and respects the assignments.
    Finally, by applying standard backtracing techniques, we can extract the spine positions of the new vertices to also obtain the layout.
    

long
We observe that there are ℓ^ ·! ·^ ·ω^ different possibilities for assignments (i)–(iv).
sectionDP
Before we show <ref>, we first make some observations on the assignments (i)–(iv) and their immediate consequences.
In the following, we only consider consistent branches, i.e., we discard branches where from assignment (ii) we get u  v but from assignment (iii) u = [[a, b]] and v = [[c, d]] with c ≺ d ≼ a ≺ b, as this implies v ≺ u.

First, we observe that assignment (i) fully determines the page assignment σ_G.
Thus, it allows us to check whether an edge e∈, i.e., a new edge incident to two old vertices, crosses any old edge or another new edge from .
From now on, we consider all edges from  as old since their placement is completely determined by assignment (i).

Second, assignments (i) and (ii) allow us to check whether two new edges e = ua, e' = vb ∈ with u,a,v,b∈ will cross each other.

Third, adding assignment (iii), we can also check this for new edges with some endpoints in V(H), i.e., extend this to all u,a,v,b∈ V(G).
Hence, assignments (ii) and (iii) together with ≺_H fix the relative order among vertices incident to new edges.
<ref> shows an example where the assignments imply a crossings among two new edges. 















All of the above checks together can be done in

^2 + · time.
Clearly, if the assignments (i)–(iv) imply a crossing in an ℓ-page stack layout of G or contradict each other, we report that no layout exists that respects assignments (i)–(iv).
However, if not, we still need to find concrete spine positions for the new vertices. 
The main challenge here is to assign new vertices to faces such that adjacent new vertices are in the same face and not two different faces with the same distance to the outer-face.
For this, we use assignment (iv) together with the following dynamic programming (DP) algorithm.



    The Intuition Behind the DP-Algorithm.

Recall that assignment (iv) determines for every new edge e ∈ the distance ω_e to the outer-face with respect to H, i.e., how many edges of H we need to remove until e lies in the outer-face of the adapted stack layout H; see also <ref>.

We first observe that ω_e together with σ and the intervals in ≺_H in which the endpoint vertices of e are placed in uniquely determine a single face, namely the one the edge e is embedded in.
Furthermore, for every possible distance ω_e ∈ [ω]_0 and every interval in ≺_H, there is at most one face on page σ(e) with distance ω_e to the outer-face that spans the interval.
Hence, we address in the following for a given interval [a, b] with a ≺_H b the face on page σ(e) at the distance ω_e to the outer-face, if it exists, with ω_e^[a, b].
Note that ω_e^[a, b] = 0 always refers to the outer-face, independent of the vertices a and b.
However, 
for two different intervals [a, b] and [a', b'] the expressions ω_e^[a, b] and ω_e^[a', b'] can identify two different faces.

As a consequence of the above observation, we can decide for each interval of ≺_H whether we can position a new vertex v there, i.e., whether v sees its adjacent vertices using the faces (in the assigned pages) at the corresponding distance from the outer-face.
We now consider the ordering of the new vertices as in , i.e., we have v_1 ≺ v_2 ≺…≺ v_.
Furthermore, we number the intervals of ≺_H from left to right and observe that there are V(H) + 1 intervals.

Consider a hypothetical solution  which we cut vertically at the ith interval of ≺_H.
This partitions the new vertices into those that have been placed left and right of the cut.
For new vertices placed in the ith interval of ≺_H, different cuts at the ith interval yield different partitions into left and right.
Furthermore, some of the new edges lie completely on one side of the cut, while others span the cut.
For j ∈ [], let G_j be the graph G[V(H) ∪{v_1, …, v_j}], i.e., the subgraph of G induced by the vertices of H and the first j new vertices.
We will refer to edges that span the cut and thereby only have one endpoint in G_j as half-edges and denote with v· a half-edge with endpoint v∈ G_j.
Let G_j^+ be G_j extended by the half-edges E_j^+ = {v_x·| v_xv_y ∈, 1 ≤ x ≤ j < y ≤}; see <ref>.

In the following, we denote with e^+ the half-edge that we create for the edge e.
For the half-edge e^+ = v_x· and the edge e = v_xv_y, we call the vertex v_x inside G_j, denoted as V_je, and the vertex v_y outside G_j, denoted as V_je.

Consider again the hypothetical solution  and its vertical cut at the ith interval.
Assume that j vertices have been placed in  left of the cut.
The stack layout  witnesses the existence of a stack layout for G_j that extends H and uses only the first i intervals.
Furthermore, for every half-edge e^+ in G_j^+ the face where e is placed in gives us a set of candidate intervals for the vertex V_je, namely those incident to that face.
Hence, we can describe a partial solution of  by a tuple (i, j).



























































































    The DP-Algorithm.

Let D be an (V(H) + 1) × ( + 1) × 2 binary table.
In the following, we denote an entry (i, j, r) for i ∈ [V(H) + 1], j ∈ [ + 1], and r ∈{0, 1} as a state of the algorithm.
A state (i, j, r) for i ∈ [V(H) + 1], j ∈ [ + 1], and r ∈{0, 1} is called feasible if and only if there exists, in the current branch, an extension of H for the graph G_j with the following properties.

    
  * The j new vertices are positioned in the first i intervals and their placement respects assignment (iii).FP]dp:feasible-j-in-i
    
  * If r = 1, the last vertex v_j has been placed in the ith interval.
    Otherwise, i.e., if r = 0, the last vertex v_j has been placed in some interval i' with i' < i.FP]dp:feasible-r
    
  * For every half-edge e^+ of G_j^+, the face in which we placed (the first endpoint of) e^+ spans the ith interval.FP]dp:feasible-half-edges





Note that for <ref>, we neither require that there exists some interval i' with i ≤ i' for the vertex V_je that is incident to ω_e^i nor that this i'th interval is part of V_je, i.e., the  for V_je according to assignment (iii).
However, we will ensure all of the above points in the DP  when placing V_je.
Furthermore, while the last (binary) dimension is technically not necessary, it simplifies our following description.
Finally, note that we (correctly, as required in some solutions) allow to position multiple vertices in the same interval of ≺_H.

Our DP will mark a state (i, j, r) for i ∈ [V(H) + 1], j ∈ [ + 1], and r ∈{0, 1} as feasible by setting D[i, j, r] = 1.
Before we can show in <ref> that our DP indeed captures this equivalence, let us first relate different states and thus also partial solutions to each other.
We observe that if we have a solution for i ∈ [V(H)], j ∈ []_0, and r ∈{0,1}, and for every half-edge e^+ of G_j^+ the face ω_e^i also spans the i + 1th interval, then we also have a solution in the state (i + 1, j, 0).
Otherwise, we cannot find an interval for the vertex V_je for some half-edge e^+ of G_j^+; see <ref>b.

More formally, let [a, b] be the ith interval and [b, c] the i + 1th interval.
Assume that we have the new edge e = v_xv_y in G with 1 ≤ x ≤ j < y ≤ k, which is the half-edge v_x· in G_j^+.
Let a'b' be the edge (on page σ_G(e)) that bounds the face identified by ω_e^i upwards with a' ≺ b ≼ b'.
We call (i, j, r) an admissible predecessor of (i + 1, j, 0) if b ≠ b'; see <ref>a.

If we decide to place the vertex v_j in the ith interval, say [a, b], we have to be more careful.
In particular, we have to ensure the following criteria before we can conclude that (i, j, 1) has an extension.

	
  * The interval [a, b] is part of the  v_j, i.e., we place the new vertex in the determined .EC]dp:extension-super-interval
	
  * For all new edges e = v_ju with u ∈ V(H) the face ω_e^i exists on the page σ_G(e) and both the interval i (and thus v_j) and u are incident to the face ω_e^i.EC]dp:extension-old-vertex
	
  * For all new edges e = v_jv_q incident to two new vertices the face ω_e^i exists on the page σ_G(e) and the interval i (and thus v_j) is incident to it.EC]dp:extension-new-vertex
	
	

The second criterion ensures that edges incident to v_j and an old vertex can be inserted without introducing a crossing.
The third criterion ensures for a new edge e incident to two new vertices that the half-edge e^+ has been completed to a full edge without introducing a crossing or is placed in the face ω_e^i that spans the ith interval (if j < q).
Similar to before, we call (i, j - 1, r) an admissible predecessor of (i, j, 1) if all of the above criteria are met.
Finally, note that if we decide to place the vertex v_j in the ith interval, then the state (i, j, 0) is not feasible due to <ref>.

Our considerations up to now are summarized by the recurrence relation in <ref>.
In <ref>, we show that the recurrence relation identifies exactly all feasible states and thus partial solutions.

	
	We have the following relation for all i ∈ [2,V(H) + 1] and j ∈ []_0.
	
    D[1, 0, 0]    = 1
    
            D[1, 0, 1]    = 0
    
    		D[i, j, 0]    = 
    			1     if (i - 1, j, r) is an admissible predecessor of (i, j, 0)
        and D[i - 1, j, r] = 1 for some r ∈{0,1}
    
    			0     otherwise
    
    		D[i, j, 1]    = 
    			1     if (i, j - 1, r) is an admissible predecessor of (i, j, 1)
        and D[i, j - 1, r] = 1 for some r ∈{0,1}
    
    			0     otherwise




lemmalemmaDPRecurrenceCorrectness
	
	For all i ∈ [V(H) + 1], j ∈ []_0, and r ∈{0,1} we have D[i, j, r] = 1 if and only if the state (i, j, r) is feasible.
	Furthermore, evaluating the recurrence relation of <ref> takes  time.


	We first use induction over i and j to show correctness of the recurrence relation and later argue the time required to evaluate it.
	In the following, we let [a, b] be the ith interval.
	
	*Base Case (i = 1 and j = 0).
	If we have i = 1 and j = 0, we are in the first interval and have not placed any new vertex.
	Thus, G_j = G_j^+ = H holds and G_j has clearly a solution, namely H.
	Furthermore, there are no half-edges in G_j^+ and thus (1, 0, r) is a feasible state if and only if r = 0.
	Note that (1, 0, 1) contradicts <ref> and thus cannot be a feasible state.
	Hence, <ref> are correct and serve as our base case.

	In our inductive hypothesis, we assume that the table D has been correctly filled up until some value i' ∈ [V(H) + 1] and j' ∈ []_0.

	*Inductive Step for i (i = i' + 1 and j = j').
	First, note that by moving one interval to the right, having r = 1 is not possible and hence we focus on <ref> in this step.
	We consider the cases D[i, j, 0] = 1 and D[i, j, 0] = 0 separately.
	
	For D[i, j, 0] = 1, there exists by the definition of <ref> an admissible predecessor (i', j, r) for some r ∈{0,1} with D[i', j, r] = 1.
	By our inductive hypothesis, this means that the state (i', j, r) is feasible.
	In particular, it has a solution for G_j that places all new vertices in the first i' intervals.
	Clearly, the same solution positions them also in the first i intervals.
	Furthermore, every half-edge e^+ of G_j^+ is assigned to a face that spans the i'th interval.
	As (i', j, r) is an admissible predecessor, we know that for every e ∈ G_j^+ the face ω_e^i' also spans the ith interval.
	Hence, the state (i, j, 0) is feasible, i.e., D[i, j, 0] = 1 correctly holds.
	
	For D[i, j, 0] = 0, there are two cases to consider by the definition of <ref>.
    Either (i, j, 0) does not have an admissible predecessor, or for all admissible predecessors (i', j, r) of (i, j, 0) we have D[i', j, r] = 0.
    Observe that only states of the form (i', j, r) for some r ∈{0,1} can be admissible predecessors.
    In the former case, there exists by our definition of admissible predecessor some half-edge e^+ in G_j^+ that is assigned to the face ω_e^i' which does not span the ith interval.
    Hence, (i, j, 0) is not feasible by <ref>.
	In the latter case, we know by our inductive hypothesis that D[i', j, r] = 0 implies that (i', j, r) is not feasible, i.e., there does not exist a solution for the graph G_j in which we place the new vertices in the first i' intervals.
	
	As we do not place the vertex v_j in the ith interval, no solution can exist for the state (i, j, 0) either and D[i, j, 0] = 0 correctly holds.
	This concludes the inductive step for i.
	
	*Inductive Step for j (i = i' and j = j' + 1).
	Analogous to before, we note that by placing v_j in the ith interval, r = 0 is not possible and hence we focus on <ref> in this step.
	We again consider the cases D[i, j, 1] = 1 and D[i, j, 1] = 0 separately.
	
	For D[i, j, 1] = 1, there exists an admissible predecessor (i, j', r) for some r ∈{0,1} with D[i, j', r] = 1 by the definition of <ref>. 
	By our inductive hypothesis, this means that the state (i, j', r) is feasible and has a solution G_j - 1 that places all new vertices of G_j - 1 in the first i intervals.
	We now construct a solution G_j by setting σ_G_j according to assignment (i), and extending the spine order ≺_G_j - 1 by placing v_j in the ith interval.
	More concretely, we take ≺_G_j - 1, set a ≺ v_j ≺ b, and take the transitive closure to obtain a linear order on the vertices of G_j.
	As (i, j', r) is an admissible predecessor, v_j is placed within v_j in G_j and G_j extends H.
	So it remains to show that G_j is crossing-free.
	As we discard all assignments (i)–(iv) that imply a crossing among two new edges, a new edge e incident to v_j could only cross an old edge e'.
	However, as (i, j', r) is an admissible predecessor, we have that the vertices incident to e lie in the same face ω_e^i.
    Every old edge induces a face of H.
    Therefore, we deduce that a crossing between an old and a new edge whose endpoints lie in the same face is impossible.
    Consequently, also e and e' cannot cross.
	Thus, G_j is a solution for the graph G_j.
	Finally, it is clear that for every half-edge e^+ of G_j^+, the face assigned to its associated edge e spans the ith interval.
	For half-edges that already existed in G_j'^+, this holds as (i, j', r) is feasible.
	For half-edges introduced in G_j^+, this holds by the definition of admissible predecessor; see <ref>.
	Thus, (i, j, 1) is feasible and D[i, j, 1] = 1 correctly holds.

    For D[i, j, 1] = 0, there are again two cases to consider by the definition of <ref>.
    Either (i, j, 1) does not have an admissible predecessor, or for all admissible predecessors (i, j', r) of (i, j, 0) we have D[i, j', r] = 0.
    Again, we observe that it suffices to consider only states of the form (i, j', r) for some r ∈{0,1} as potential admissible predecessors.
    For the former case, clearly, if both such states (i, j', r) are not admissible predecessors, then (i, j, 1) cannot be feasible:
	Either, we violate <ref> by placing v_j outside v_j, which contradicts assignment (iii), or an edge e incident to v_j crosses an old edge as one of its endpoints is not incident to ω_e^i; see <ref>.
	Note that we can assume that all relevant faces span the ith interval, as we have already shown that the inductive step for i is correct.
	In both cases, (i, j, 1) is clearly not feasible; see <ref> for the former and observe that a crossing contradicts the existence of an extension for the latter case.
	We now consider the case where all admissible predecessor (i, j', r) of (i, j, 1) have D[i, j', r] = 0.
	Using proof by contradiction, we show that in this case (i, j, 1) cannot be feasible either.
	Assume that (i, j, 1) would be a feasible state.
	Then, there exists a solution G_j for the graph G_j.
    Using G_j, we can create a solution G_j' for G_j' by removing v_j from ≺_G_j and all its incident edges from σ_G_j.
	Clearly, G_j' respects the assignments (i)–(iv).
	Furthermore, for every half-edge e^+ in G_j^+, the assigned face spans the ith interval as (i, j, 1) is feasible; see <ref>.
	For every half-edge e^+ in G_j'^+ with V_j'e = v_j, i.e., that was completed to an ordinary edge in G_j, the assigned face spans the ith interval as it is incident to it.
	Hence, if (i, j, 1) is feasible and (i, j', r) is an admissible predecessor, then (i, j', r) is also feasible.
	However, this contradicts the inductive hypothesis, as we have D[i, j - 1, r] = 0.
	Thus, the state (i, j, 1) cannot be feasible and D[i, j, 1] = 0 correctly holds.
	
	
	
	
	This concludes the inductive step for j.
	
	*Evaluation Time of Recurrence Relation.
	We observe that, apart from checking whether a state is an admissible predecessor of (i, j, r), the steps required to perform in order to evaluate the recurrence relation take constant time.
	In the following, we assume that we can access a look-up table that stores the faces in H that span a given interval in ≺_H  on a given page p ∈ [ℓ] ordered from outside in, i.e., starting with the outer-face.
	We will account for this in our proof of <ref>.
	In <ref>, we ensure for every half-edge e^+ in G_j^+ that the face ω_e^i - 1 does not end at the interval i - 1.
	As there are at most  half-edges, we can do this in  time.
	For <ref>, we have to ensure that the ith interval [a, b] is part of v_j, which takes constant time.
	Furthermore, we have to check for every new edge e = v_ju that the face ω_e^i exists on the page σ(e) and that v_j is incident to it.
	For a single edge, this takes constant time, as we can look up the faces that span the ith interval and v_j is always incident to the bottom-most face.
	Furthermore, if u ∈ V(H) holds, we also have to check if u is incident to ω_e^i.
	If u ≼ a ≺ b, we can access the faces that span the interval [u, ≺_Hu] and check if u is incident to the face ω_e^i.
    An analogous check can be made if we have a ≺ b ≼ u.
	This takes constant time per edge e.
	Hence, we can evaluate <ref> in  time.
	Combining all, the claimed running time follows.



    Putting Everything Together.

With our DP at hand, we are now ready to prove <ref>.

    First, recall that we can check in 
    
    ^2 +  · 
    time whether assignments (i)–(iv) are consistent and do not imply  a crossing.
    
    Thus, we assume for the remainder of the proof that they are.
    Furthermore, recall that there are V(H) + 1 intervals in H and observe that we have G_k = G_k^+ = G.
    Therefore, G_k^+ does not not contain any half-edge and the feasibility propery <ref> is trivially satisfied.
    Hence, as a consequence of <ref>, we deduce that there exists an ℓ-page stack layout of G that extends  and respects assignments (i)–(iv) if and only if D[V(H)  + 1, , r] = 1 for r = 0 or r = 1.
    Furthermore, by applying standard backtracing techniques, we can also determine the concrete spine positions for every new vertex, i.e., compute such a stack layout.

    We now bound the running time of the DP.
    For that, we first observe that the DP-table D has ·V(H) entries.
	We have seen in <ref> that the time required to evaluate the recurrence relation is in .
	However, we assumed that we have access to a lookup-table that stores for each interval and each page the faces that span it.
	We can compute this table in a pre-processing step by iterating from left to right over the spine order ≺_H and keeping at each interval [a, b] for each page p track of the edges a' b' with σ(a'b') = p and a' ≼ a ≺ b ≼ b.
	This can be done in ^2 time.
    However, as this table can be re-used in different invocations of the DP-Algorithm, it has to be computed only once in the beginning.
    As the overall running time of the -algorithm will clearly dominate ^2, we neglect this pre-computation step.
	Hence, the running time of the DP is  ·V(H) · and together with the initial checks, this amounts to ·· time.


long
Finally, we observe that for assignment (i), i.e., σ_G, there are ℓ^ different possibilities, for assignment (ii), i.e., , there are ! possibilities, for assignment (iii), i.e., the assignment of new vertices to , there are ^ possibilities, and for assignment (iv), i.e., the distance to the outer face, there are ω^ different possibilities.
This gives us overall ℓ^ ·! ·^ ·ω^ different possibilities for assignments (i)–(iv). 

long
Applying <ref> to each of these, we get the desired theorem:
*

Applying <ref> to each of these, we get the following theorem.





	







	






	



























































	














    



	

































	

















	


	
























































	

















	


	


















long



§ TOWARDS A TIGHTER FIXED-PARAMETER ALGORITHM FOR 


As a natural next step, we would like to generalize <ref> by considering only κ and ℓ as parameters.
However, the question of whether one can still achieve fixed-parameter tractability for when parameterizing by κ+ℓ is still open.
Nevertheless, as our final result, we show that strengthening <ref> is indeed possible at least in the restricted case where no two missing vertices are adjacent, as we can then greedily assign the first “possible” interval to each vertex that complies with assignment (i)–(iii).

ptheoremIndependentSetFPT








Observe that G[] being an independent set removes the need for synchronizing the position of adjacent new vertices to ensure that they are incident to the same face.
We propose a fixed-parameter algorithm that loosely follows the ideas introduced in  <ref> and adapts them to the considered setting.


The following claim will become useful.

    
    Given an instance = of  where G[] is an independent set,
(i) a page assignment σ_G for all edges,
(ii) an order  in which the new vertices will appear along the spine, and
(iii) for every new vertex v ∈ an assignment to a .
    In 
     ·^2 
    time we can compute an ℓ-page stack layout of G that extends  and respects the given assignments (i)–(iii) or report that no such layout exists.

Towards showing the claim, we first note that we only miss assignment (iv) from <ref>.
    Hence, by the same arguments as in the proof of <ref>, we can check in 
    ^2 + ·
    time whether assignments (i)–(iii) are consistent and do not imply a crossing.
    For the remainder of the proof, we assume that they are, as we can otherwise immediately return that there does not exist an ℓ-page stack layout of G that respects the assignments.

    We still need to to assign concrete spine positions to new vertices.
    However, in contrast to <ref>, there is no need to ensure that adjacent new vertices are in the same face, because there are no two new vertices are adjacent by assumption.
    This allows us to use a greedy variant of the DP from <ref>.

    The Greedy Algorithm.
    We maintain a counter j initialized at j = 1 and consider the ith interval [a, b].
    If [a, b] ∈v_j, i.e., if [a, b] is part of the  for v_j, we check the following for every new edge e = v_ju ∈ incident to v_j.
    Assuming that v_j would be placed in [a, b], we check whether v_j sees u on the page σ(e).
    
    These checks can be done in · time.
    If this is the case, we place v_j in the interval [a, b] and increase the counter by one, otherwise we continue with the next interval [b, c].
    We stop once we have j = k + 1 as we have assigned an interval to all new vertices.
    To obtain the ℓ-page stack layout of G, we can store in addition for each vertex the interval we have placed it in.
    If after processing the last interval there are still some new vertices that have not been placed, we can return that there does not exist an ℓ-page stack layout of G that extends H and respects the assignments (i)—(iii).
    
    The greedy algorithm runs in  ·^2 time.
    

    Correctness of the Greedy Algorithm.
    In the following, we show that if there is an ℓ-page stack layout of G that extends H and respects assignments (i)–(iii), then our greedy algorithm finds also some.
    To that end, we assume that there is such a stack layout ⟨≺^*_G, σ^*_G⟩.
    As we only assign intervals and thus spine positions to the new vertices, it suffices to show that if ⟨≺^*_G, σ^*_G⟩ is a solution, so is ⟨≺, σ^*_G⟩, where ≺ is the spine order we obtain with our greedy algorithm.
    Observe that we must find some tuple G that extends H and respects the assignments (i)–(iii), as we only ensure that no new edge incident to a new vertex crosses old edges.
    As this is clearly not the case in ⟨≺^*_G, σ^*_G⟩, there must be a feasible interval for each new vertex.
    For the remainder of the proof, we assume that ≺^*_G and ≺ differ only in the position of some new vertex v.
    This is without loss of generality, as we can apply the following arguments for all new vertices iteratively from left to right according to ≺^*_G, until all of them are placed as in the greedy solution.
    As we assign the intervals greedily, we assume that v ≺^*_G u implies v ≺ u for all old vertices u, i.e., v appears in ≺ earlier than in ≺^*_G.
    Clearly, ⟨≺, σ^*_G⟩ extends H as ⟨≺^*_G, σ^*_G⟩ does.
    Therefore, we only need to show that ⟨≺, σ^*_G⟩ does not contain crossings.
	
    Towards a contradiction, assume that ⟨≺, σ^*_G⟩ contains a crossing among the edges e = vu and e' = ab.
    We assume that e is a new edge incident to the new vertex v and observe that u must be an old vertex.
    Furthermore, we assume without loss of generality that b is also an old vertex.
    As already argued in the beginning, we have checked, when placing v, that e does not cross an old edge.
    Hence, we observe that e' cannot be an old edge.
    As we also treated all new edges incident to two old vertices as old edges, we conclude that e' must be a new edge incident to a new vertex a and an old vertex b.
    Furthermore, we assume a ≺^*_G b, a ≺^*_G v, and v ≺^*_G u.
    This is without loss of generality, as in any other case the arguments will be symmetric.
    As ⟨≺^*_G, σ^*_G⟩ is crossing free, we have a ≺^*_G b ≺^*_G v ≺^*_G u or a ≺^*_G v ≺^*_G u ≺^*_G b.
    Furthermore, as our greedy algorithm positions v further to the left compared to ≺^*_G and e and e' now cross, we must have a ≺ v ≺ b ≺ u or v ≺ a ≺ u ≺ b, respectively.
    However, we observe that neither situation is possible.

    For the former case, i.e., when we turn a ≺^*_G b ≺^*_G v ≺^*_G u into a ≺ v ≺ b ≺ u, we observe that b is an old vertex incident to a new edge, i.e., it defines a , see also <ref>a.
    Hence, having b ≺^*_G v and v ≺ b implies that the  for v differs between ⟨≺^*_G, σ^*_G⟩ and ⟨≺, σ^*_G⟩, which violates assignment (iii) and thus contradicts our assumption on the existence of ⟨≺^*_G, σ^*_G⟩ and ⟨≺_G, σ^*_G⟩.
    
    In the latter case, when we turn a ≺^*_G v ≺^*_G u ≺^*_G b into v ≺ a ≺ u ≺ b, we move v left of the new vertex a.
    Hence, we change the relative order among the new vertices, see <ref>b.
    This is a contradiction to assignment (ii) and thus our assumption on the existence of ⟨≺^*_G, σ^*_G⟩ and ⟨≺_G, σ^*_G⟩.
	
    As we obtain in all cases a contradiction, we conclude that e and e' cannot cross.
    Applying the above arguments inductively, we derive that our algorithm must find a solution if there exists one, i.e., is correct.

    *Putting Everything Together.
    We can now branch over all possible assignments (i)—(iii).
    For assignment (i), i.e., σ_G, there are ℓ^ different possibilities, for assignment (ii), i.e., , there are ! possibilities, and for assignment (iii), i.e., the assignment of new vertices to , there are ^ possibilities
    This gives us overall ℓ^ ·! ·^ different possibilities for assignments (i)–(iii).
    Applying our greedy algorithm to each of them, we obtain the theorem.

figFPTISCorrectness





§ CONCLUDING REMARKS


Our results provide the first investigation of the drawing extension problem for stack layouts through the lens of parameterized algorithmics. We show that the complexity-theoretic behavior of the problem is surprisingly rich and differs from that of previously studied drawing extension problems. One prominent question left for future work is whether one can still achieve fixed-parameter tractability for when parameterizing by κ+ℓ, thus generalizing <ref>long and <ref>As our final result, we show that this is indeed possible at least in the restricted case where no two missing vertices are adjacent, as we can then greedily assign the first “possible” interval to each vertex that complies with assignment (i)–(iii).

.
A further natural and promising direction for future work is to consider generalizing the presented techniques to other types of linear layouts, such as queue layouts.
Finally, future work could also investigate the following generalized notion of extending linear layouts:
Given a graph G, the spine order for some subset of its vertices and the page assignment for some subset of its edges, does there exist a linear layout of G that extends both simultaneously?














long
    

§ OMITTED PROOFS FROM SECTION <REF>


    *
    
    

    *
    
    

    

§ OMITTED DETAILS FROM SECTION <REF>


    

    

 §.§ Omitted Proofs

    *
    
    

    *
    
    

    
    

    

§ OMITTED DETAILS FROM SECTION <REF>

    

	

    
    
    

    

 §.§ Omitted Proofs

    *
    
    

    

§ OMITTED DETAILS FROM SECTION <REF>


    The main task left open in <ref> was the proof of the following lemma.
    *
    
    In the following, we use the following notation related to .
    

    *
    
    
        We observe that for assignment (i), i.e., σ_G, there are ℓ^ different possibilities, for assignment (ii), i.e., , there are ! possibilities, for assignment (iii), i.e., the assignment of new vertices to , there are ^ possibilities, and for assignment (iv), i.e., the distance to the outer face, there are ω^ different possibilities.
        This gives us overall ℓ^ ·! ·^ ·ω^ different possibilities for assignments (i)–(iv). 
        The theorem thus follows by applying <ref> to each of these.
    

    

§ OMITTED DETAILS FROM SECTION <REF>


    In <ref>, we stated the following theorem, which we now want to prove.
    *
    
    

    





    
    

    
    
    

    

    
    

    
    
    

    
    
    




§ REMOVING MULTI-EDGES


In the following section, we will describe how one can adapt the - and [1]-hardness reductions to not rely on multi-edges.
While the basic idea is always the same, namely to introduce several auxiliary vertices in order to distribute the multiple edges among them, the concrete implementation depends on the (part of) the reduction we are currently discussing, see the following sections.



 §.§ Fixation Gadget (Section <ref>)


While the fixation gadget gives us a lot of power to show hardness of different parameter combinations, we use multi-edges to construct it.
As our graphs H and G are assumed to be simple, it is now time to remove these multi-edges by distributing them over several (additional) auxiliary vertices.

In order to do that, we no longer introduce the 2(F + 1)-many vertices b_1, …, b_F + 1 and a_1, …, a_F + 1, but introduce for each page p ≠ p_d 2(F + 1) vertices b_1^p, …, b_F + 1^p and a_1^p, …, a_F + 1^p.
We also adapt the spine order ≺_H and set b_i^p ≺ v_i ≺ a_i^p for i ∈ [F + 1] and p ∈ [ℓ] ∖{p_d}.
Furthermore, we fix the order among the newly introduced vertices by enforcing b_i^p + 1≺ b_i^p and a_i^p ≺ a_i^p + 1 for every i ∈ [F + 1] and p ∈ [ℓ] ∖{p_d}.
The linear order ≺ is then obtained by taking the transitive closure of the above (partial) orders.
Observe that the above spine order places for each page p one vertex before (b_i^p) and after  (a_i^i) v_i.

Next, we adapt the edges that we created in <ref> and their page assignment σ_H.
To that extend, recall that we introduced for every i ∈ [F + 1] and every page p ≠ p_d the edge e(b_i, a_i, p) = b_ia_i with σ(e(b_i, a_i, p)) = p.
Now, this edge should be incident to vertices created “for the page p”, i.e., we create instead the edge b_i^pa_i^p and set σ(b_i^pa_i^p) = p.
Although the remaining edges created in <ref> are already simple, we have to adapt (some of) them, as their incident vertices no longer exist, i.e., have been replaced.
In particular, for every i ∈ [F + 1], we now no longer introduce the edges b_iv_i and v_ia_i but the edges b_i^ℓ - 1v_i and v_ia_i^ℓ - 1 and set σ(b_i^ℓ - 1v_i) = σ(v_ia_i^ℓ - 1) = p_d.
Finally, we create instead of the edge b_1a_F + 1 the edge b_1^ℓ - 1a_F + 1^ℓ - 1 and set σ(b_1^
ℓ - 1a_F + 1^ℓ - 1) = p_d.
<ref> is an adapted version of <ref> and shows the updated construction.

We end this section with showing <ref>, which is an adapted version of <ref>.

	
	Let = be an instance of  that contains the adapted fixation gadget (without multi-edges) on F vertices {f_1, …, f_F}.
	In any solution G to  and for every i ∈ [F], we have v_i ≺ f_i ≺ v_i + 1 and σ(f_iv_i) = σ(f_iv_i + 1) = p_d.
	Furthermore, the adapted fixation gadget contributes 2Fℓ + 2ℓ - 1 vertices and (ℓ + 4)F + ℓ + 2 edges to the size of .


	Let G be a solution to .
	Regarding the two properties of any possible solution to , i.e., that v_i ≺ f_i ≺ v_i + 1 and σ(f_iv_i) = σ(f_iv_i + 1) = p_d holds for every i ∈ [F], it suffices to make the following observations in the proof of <ref>.
	
	We first consider the argument we made to show v_i ≺ f_i ≺ v_i + 1.
    There, we first assumed that f_i ≺ v_i would hold for an i ∈ [F].
	Using the observation on the presence of the edges e(b_i + 1, a_i + 1, p) for every page p ≠ p_d and the spine order b_i + 1≺_H v_i + 1≺_H a_i + 1, we concluded that f_i can see v_i + 1 only on the page p_d.
	This ultimately led to a contradiction to the assumption on the existence of a solution with f_i ≺ v_i.
	Now, for the modified fixation gadget we can make a similar observation.
	Consider any page p ≠ p_d.
	The graph H contains the edge b_i + 1^pa_i + 1^p and we have b_i + 1^p ≺_H v_i + 1≺_H a_i + 1^p.
	Hence, f_i can still see v_i + 1 only on the page p_d, i.e., we still must have σ(f_iv_i + 1) = p_d.
	And by the very same arguments as in the proof of <ref> this leads to a contradiction.
	
	Let us now re-visit the argument to show σ(f_iv_i) = σ(f_iv_i + 1) = p_d.
    There, we assumed the existence of a solution  with σ(f_iv_i) ≠ p_d for some i ∈ [F], i.e., we assumed that σ(f_iv_i) = p holds for some page p ≠ p_d.
	Under this assumption, we (again) make the observation that we have the edge b_i^pa_i^p with σ_H(b_i^pa_i^p) = p, which allows us to strengthen above result to v_i ≺ f_i ≺ a_i^p.
	As in the proof of <ref>, we deduce from σ_H(v_ia_i^ℓ - 1) = p_d and σ_H(b_i + 1^p'a_i + 1^p') = p' for any page p' ≠ p_d that there does not exist a feasible page assignment for the edge f_iv_i + 1, which leads to a contradiction as in the proof of <ref>.
	
	Regarding the size of the adapted fixation gadget, we first observe that we have not introduced any additional edge, but rather re-distributed existing edges to additional vertices.
	For the number of vertices in the adapted fixation gadget, we recall that ℱ consists of F vertices and we have F + 1 vertices of the form v_i.
	As we introduce 2(F + 1) vertices per page p ≠ p_d, this amounts to 2(F + 1)(ℓ - 1) additional vertices.
    Combining all, we conclude that we have 2Fℓ + 2ℓ - 1 vertices in the adapted fixation gadget. 




 §.§ -hardness Reduction (Section <ref>)


Our reduction from <ref> that we used to show that  with two new vertices is -complete, see <ref>, creates a graph H with several multi-edges.
More concretely, we created multi-edges both in the base layout from <ref>, for example to block visibility to a vertex, and in the fixation gadget.
For the latter part of the reduction, i.e., the fixation gadget, we have discussed in <ref> how to remove the multi-edges.
This section is devoted to describe a way to remove the multi-edges in the former part, i.e., the base layout.
At the end of this section, we argue that our reduction remains correct.



    Removal of the Multi-Edges.

Let φ = (𝒳, 𝒞) be an instance of  with N = 𝒳 variables and M = 𝒞 clauses.
Recall that we introduced N + M + 1 dummy vertices d_q in <ref> and distributed them in ≺_H on the spine, i.e., we set d_i ≺ x_i ≺ d_i + 1 and d_N + j≺ c_j ≺ d_N + j + 1 for every i ∈ [N] and j ∈ [M].
We now create 2N(N + M + 1) dummy vertices d_q^p instead with q ∈ [N + M + 1] and p ∈ [2N], i.e., N + M + 1 dummy vertices for every page p ∈ [ℓ] ∖{p_d} associated to a variable.
These new dummy vertices are ordered on the spine as follows.
We set d_i^p ≺ x_i ≺ d_i + 1^p and d_N + j^p ≺ c_j ≺ d_N + j + 1^p for every i ∈ [N], j ∈ [M], and p ∈ [2N].
Furthermore, we set d_q^p_i≺ d_q^p_¬ i for every q ∈ [N + M + 1] and i ∈ [N].
Finally, we set d_q^p_¬ i≺ d_q^p_i + 1 for every q ∈ [N + M + 1] and i ∈ [N - 1].
We obtain the linear order ≺_H by taking the transitive closure of the above relative orders, see also <ref>.


Next, we redistribute the multi-edges over the new dummy vertices.
Recall that we created for every pair of variables x_i, x_j ∈𝒳 with i ≠ j the edges e(x_i, p_j) = d_id_i + 1 and e(x_i, p_¬ j) = d_id_i + 1.
Now, we create the edges e(x_i, p_j) = d_i^p_jd_i + 1^p_j and e(x_i, p_¬ j) = d_i^p_¬ jd_i + 1^p_¬ j instead.
We leave the page assignment σ_H as it is, i.e., we have σ(e(x_i, p_j)) = p_j and σ(e(x_i, p_¬ j)) = p_¬ j.
Furthermore, we created for every combination of a clause c_j ∈𝒞 and a variable x_i ∈𝒳 edges depending on the occurrence of x_i in c_j.
We now also re-distribute these edges as follows.
If x_i does not appear in c_j, we create the edges e(c_j, p_i) = d_N + j^p_id_N + j + 1^p_i and e(c_j, p_¬ i) = d_N + j^p_¬ id_N + j + 1^p_¬ i.
We set σ(e(c_j, p_i)) = p_i and σ(e(c_j, p_¬ i)) = p_¬ i.
If x_i appears in c_j without negation, we create the edge e(c_j, p_i) = d_N + j^p_id_N + j + 1^p_i and set σ(e(c_j, p_i)) = p_i.
Symmetrically, if x_i appears negated in c_j, we create the edge e(c_j, p_¬ i) = d_N + j^p_¬ id_N + j + 1^p_¬ i and set σ(e(c_j, p_¬ i)) = p_¬ i.

Finally, we set a_3^p_ℓ - 1≺ d_1^p_1 to ensure that the (in <ref> adapted) fixation gadget is placed at the very beginning of the spine.
Furthermore, we add the edge d_1^p_1d_N +M + 1^p_¬ N and set σ(d_1^p_1d_N +M + 1^p_¬ N) = p_d to ensure that our adapted construction still has <ref>.



    Correctness of the Reduction.

First, observe that we added a polynomial number of additional vertices to H and no new edges.
Hence, the size of H (and G) increased by a factor polynomial in the size of φ and the size of  remains polynomial in the size of φ.
Furthermore, due to <ref>, it still holds that in any solution G to  we have s ≺ v ≺ d_1^p_1≺ x_i ≺ c_j ≺ d_N + M + 1^p_¬ N for every i ∈ [N] and j ∈ [M].
Similarly, the relative position in ≺_H of the dummy vertices on the spine in the adapted reduction did not change compared to the reduction from <ref>, i.e., instead of d_i ≺ x_i ≺ d_i + 1 and d_N + j≺ c_j ≺ d_N + j + 1 we now have d_i^p ≺ x_i ≺ d_i + 1^p and d_N + j^p ≺ c_j ≺ d_N + j + 1^p for every i ∈ [N] and j ∈ [M] (and p ∈ [2N]).
Furthermore, the edges span over the same vertices.
Hence, we conclude that the proof of <ref> readily carries over, i.e., <ref> also holds for our modified construction that does not have multi-edges.



 §.§ [1]-hardness Reduction (Section <ref>)


The reduction we have discussed in <ref> has one catch: While we only consider simple graphs as input, the graph H we construct contains multi-edges.
Although we remove already some multi-edges when incorporating the adapted fixation gadget from <ref>, some multi-edges are also introduced in <ref>.
In particular, consider the case where we have two edges u_α^iu_β^j, u_α^i'u_β^j'∈ E(G_C).
Then, for a γ∈ [k] ∖{α, β}, we would create twice the edge u_γ^1u_γ^n_γ + 1 but assign them to different pages.
In this section, we remove these multi-edges by using the additional (dummy) vertices that we obtain from the adapted fixation gadget, 
However, note that this will not effect our intended equivalence from <ref> between a solution G to  and a solution 𝒞 to .

In the following, we extend in <ref> the base layout of our reduction to accommodate the additional vertices for the adapted fixation gadget.
In <ref>, we describe how to distribute the multi-edges from <ref> across the new vertices.
Finally, we argue in <ref> that our reduction is still correct.



  §.§.§ Adapting the Base Layout of our Reduction


We now extend the base layout from <ref> by additional vertices that in the end will be identified with their respective “partner” in the (adapted) fixation gadget.
For each edge e ∈ E(G_C) and color α∈ [k + 1], we create the vertices b_α^e and a_α^e.
To order these additional vertices on the spine, we assume that the edges E(G_C) are ordered, i.e., that we have E(G_C) = {e_1, …, e_M}.
We use this ordering to extend the spine order ≺_H as follows, where we assume u_0^n_0 + 1 = u_0^0 for ease of notation.
For all α∈ [k + 1] and i ∈ [M], we set u_α-1^n_α - 1 + 1≺ b_α^e_i≺ u_α^0 ≺ a_α^e_i≺ u_α^1.
Furthermore, for j ∈ [M - 1], we also set b_α^e_j + 1≺ b_α^e_j≺ a_α^e_j≺ a_α^e_j + 1.




Informally speaking, according to the above spine order, we place for each edge e ∈ E(G_C) and each α∈ [k + 1] one vertex before (b_e^α) and after  (a_e^α) u_α^0.
The vertices before u_α^0 are ordered decreasingly by the index of their respective edge and the vertices after u_α^0 are ordered increasingly by the index of their respective edge.
To obtain the adapted linear order ≺_H we take the transitive closure of the above relation and the relations from <ref>.

Finally, we (re-)introduce the (adapted) fixation gadget on F = k vertices ℱ = 𝒳 by identifying the following vertices for α∈ [k + 1]. Note that we use i = α to distinguish between the vertices of the fixation gadget and hardness reduction.
As in <ref>, we identify v_i = u_α^0.
For the other vertices, we identify b_i^p = b_i^e_p, and a_i^p = a_α^e_p, i.e., the vertices for the pth edge e_p ∈ E(G_C) are identified with the vertices for page p in the fixation gadget.
The edges of the fixation gadget are adapted accordingly.




  §.§.§ Redistributing the Multi-Edges


While incorporating the adapted fixation gadget removes some of the multi-edges, we still have to deal with the multi-edges introduced in <ref>, where we encoded the adjacencies from G_C into H.
We do this now by redistributing the edges over the new vertices introduced in <ref> and visualize our process with <ref>.


Let e = v_α^iv_β^j∈ E(G_C) be an edge of G_C and assume α < β.
Recall that we created in <ref> a set of edges in H dedicated to e and assigned them with σ_H to the page p_e.
In particular, we created for every γ∈ [k] ∖{α, β} the edge u_γ^1u_γ^n_γ + 1.
This edge is replaced by the edges a_γ^eu_γ^1, a_γ^eb_γ + 1^e, and u_γ^n_γ + 1b_γ + 1^e, as in <ref>a.
Furthermore, we created the edges u_α^1u_α^i and u_α^i + 1u_α^n_α + 1.
Instead, we now create the edges a_α^eu_α^1 and a_α^eu_α^i, and u_α^i + 1b_α + 1^e and u_α^n_α + 1b_α + 1^e as shown in <ref>b.
Similarly, we also create the edges a_β^eu_β^1, a_β^eu_β^j, u_β^j + 1b_β + 1^e, and b_β + 1^eu_β^n_β + 1.
All of these edges are assigned to the page p_e.
Observe that for i ∈{1, n_α} or j ∈{1, n_β}, above edges would become multi-edges (on the same page), which can easily be avoided.
Recall that we created in <ref> a tunnel on the page p_e by adding the edges u_α^iu_β^j + 1 and u_α^i + 1u_β^j, see also <ref>c.
We do not need to adapt these edges, as they can only result in multi-edges if G_C would contain them.
One can readily verify that we no longer introduce multi-edges while still ensuring that the page p_e is crossing free.

Finally, recall that with the original version of the fixation gadget, we had for α∈ [k + 1] the edges u_α^0u_α^0 and u_α^0u_α^0 that were assigned to the page p_d.
In particular, these edges corresponded for α∈ [k] to the edges u_α^0u_α^1 and u_α^n_α + 1u_α + 1^0.
However, these edges are no longer present in the adapted reduction, since no vertex of the (adapted) fixation gadget is identified with the vertices u_α^1 or u_α^n_α + 1.
As above edges facilitated the arguments that showed correctness of our approach, we re-introduce them in H as follows.
For every α∈ [k], we add the edges u_α^0u_α^1 and u_α^n_α + 1u_α + 1^0 and set σ(u_α^0u_α^1) = σ(u_α^n_α + 1u_α + 1^0) = p_d.
As the above edges span the respective edges u_α^0a_α^p_e_M and b_α + 1^p_e_Mu_α + 1^0, they do not introduce crossings on the page p_d.




  §.§.§ Showing Correctness of the Modified Reduction


This completes the adaptions we need to make to our reduction and it remains to show that <ref> still holds.
Regarding the size of the created instance, it is sufficient to observe that we introduce 2(k + 1)M additional vertices (for the adapted fixation gadget, see also <ref>), and for each edge of G_C we introduce a constant number of additional edges to the already existing ones.
Thus, the size of the instance  remains polynomial in the size of G_C and we still have κ = 3k + k2.
So it remains to show the correctness of the reduction.

For that, we can, on the one hand, observe that the transformation of a solution 𝒞 to an instance of  to a solution G to the created instance of  as described for the “(⇒)-direction” in the proof of <ref> is unaffected by the changes we made.
One way to see this is that all the additional edges that we introduced run between vertices in placed between u_α^0 and u_α^1] or u_α^n_α + 1 and u_α + 1^0 for the corresponding α∈ [k + 1].
Furthermore, if we changed existing edges, then we moved their incident vertices from u_α^1 or u_α^n_α + 1 to a vertex in the above range.
However, we created the spine order ≺_G such that u_α^1 ≺ x_α≺ u_α^n_α + 1 holds.
Hence, the relative order ≺_G (and thus ≺_H) among two new vertices x_α and x_β with α, β∈ [k], or a new vertex x_α and an old vertex u_β^i with α, β∈ [k], α≠β, and i ∈{0, 1, n_β + 1} remains untouched.
Hence, G is crossing free and thus a solution to our instance of .

On the other hand, for the “(⇐)-direction”, we used the fact that the created instance  of  fulfills <ref> to construct the solution 𝒞.
Hence, if we can convince ourselves that  still fulfills said properties, then the arguments we gave in <ref> will readily carry over.
Recall that <ref> is defined as follows.
*
To see that we still have this property, we can observe that we incorporated in <ref> the adapted fixation gadget on k vertices into our construction.
As we identify, for α∈ [k], v_i = u_α^0 and f_i = x_α for i = α, <ref> follows directly from <ref>.

Recall that we introduced at the end of <ref> for every α∈ [k] the edges u_α^0u_α^1 and u_α^n_α + 1u_α + 1^0 that are placed on the dummy page p_d.
We now use these edges to make the following observation.
From <ref>, we get that we have in any solution G and for every α∈ [k] that σ(x_αu_α^0) = σ(x_αu_α + 1^0) = p_d holds.
From <ref>, that still holds in our construction, we get u_α^0 ≺ x_α≺ u_α + 1^0 for every α∈ [k].
Using the above-mentioned edges on page p_d, we observe that we cannot have u_α^0 ≺ x_α≺u_α^1 or u_α^n_α + 1≺ x_α≺ u_α + 1^0, as this would introduce a crossing on the page p_d.
Thus, our construction not only fulfills <ref>, but, furthermore, <ref> still applies.
We will now argue that our construction also fulfills <ref>, which is defines as follows.
*
To see that <ref> still holds, we first apply <ref>.
This allows us to conclude that we have u_α^1 ≺ x_α≺ u_α^n_α + 1 and u_β^1 ≺ x_β≺ u_β^n_β + 1.
Then, by exchanging u_α^0 with a_α^e and u_α + 1^0 with b_α + 1^e in the proof of <ref>, we can exclude u_α^1 ≼ x_α≼ u_α^i and u_α^i + 1≼ x_α≼ u_α + 1^0.
Therefore, we derive that x_α must be placed in v_α^i and analogously must x_β be placed in v_β^i, i.e., our construction still fulfills <ref>.

We use this now to argue that the “(⇐)-direction” of our reduction is still correct.


    Correctness of the “(⇐)-direction” in the Reduction.

We perform the arguments as in the “(⇐)-direction” of the proof of <ref>.
Most of the arguments are implied by <ref>, which are also fulfilled in our adapted reduction.
However, in the proof of <ref> we argued that the pre-requisites for <ref> are fulfilled.
In the following, we make this argument for our adapted construction.
Let us again assume that x_α and x_β are placed in v_α^i and v_β^j, respectively.
We again consider the edge x_αx_β∈ E(G) and the page p it is placed in the solution G.
By the very same arguments as in the proof of <ref>, we can exclude p = p_d.
Furthermore, as we have σ_H(a_α^eb_α + 1^e) = p_e and a_α^e ≺ u_α^1 ≺ x_α≺ u_α^n_α + 1≺ b_α + 1^e≺ x_β for an edge e  = uv ∈ E(G_C) with u ∉V_α and v ≠ V_α we get that p = p_e for an edge e ∈ E(G_C) ∩ (V_α× V_β) must hold.
This shows that all prerequisites for <ref> are fulfilled.
Hence, we obtain that the edge x_αx_β can only be placed in the page p_e that we created for the edge v_α^iv_β^j.
Hence, v_α^i and v_β^j are adjacent in G_C and the proof of the “(⇐)-direction” in <ref> readily carries over.

Combining all, we conclude that <ref> also holds for our modified construction that does not have multi-edges.




















































































