Mixed Linear Layouts: Complexity, Heuristics, and Experiments

Abstract

A k-page linear graph layout of a graph G = (V,E) draws all vertices along a line and each edge in one of k disjoint halfplanes called pages, which are bounded by . We consider two types of pages. In a stack page no two edges should cross and in a queue page no edge should be nested by another edge. A crossing (nesting) in a stack (queue) page is called a conflict. The algorithmic problem is twofold and requires to compute (i) a vertex ordering and (ii) a page assignment of the edges such that the resulting layout is either conflict-free or conflict-minimal. While linear layouts with only stack or only queue pages are well-studied, mixed s-stack q-queue layouts for s, q ≥ 1 have received less attention. We show NP-completeness results on the recognition problem of certain mixed linear layouts and present a new heuristic for minimizing conflicts. In a computational experiment for the case s, q = 1 we show that the new heuristic is an improvement over previous heuristics for linear layouts.