Mixed Linear Layouts: Complexity, Heuristics, and Experiments

08/23/2019
by   Philipp de Col, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset