Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms

Abstract

In spite of the extensive study of stack and queue layouts, many fundamental questions remain open concerning the complexity-theoretic frontiers for computing stack and queue layouts. A stack (resp. queue) layout places vertices along a line and assigns edges to pages so that no two edges on the same page are crossing (resp. nested). We provide three new algorithms which together substantially expand our understanding of these problems: 1. A fixed-parameter algorithm for computing minimum-page stack and queue layouts w.r.t. the vertex integrity of an n-vertex graph G. This result is motivated by an open question in the literature and generalizes the previous algorithms parameterizing by the vertex cover number of G. The proof relies on a newly developed Ramsey pruning technique. Vertex integrity intuitively measures the vertex deletion distance to a subgraph with only small connected components. 2. An n^O(qℓ⁾ algorithm for computing ℓ-page stack and queue layouts of page width at most q. This is the first algorithm avoiding a double-exponential dependency on the parameters. The page width of a layout measures the maximum number of edges one needs to cross on any page to reach the outer face. 3. A 2^O(n⁾ algorithm for computing 1-page queue layouts. This improves upon the previously fastest n^O(n⁾ algorithm and can be seen as a counterpart to the recent subexponential algorithm for computing 2-page stack layouts [ICALP’24], but relies on an entirely different technique.