Mixed Linear Layouts: Complexity, Heuristics, and Experiments

Philipp de Col, Fabian Klute, Martin Nöllenburg

A $k$-page linear graph layout of a graph $G=(V,E)$ draws all vertices along a line $\ell$ and each edge in one of $k$ disjoint halfplanes called pages, which are bounded by $\el…