Mixed Linear Layouts: Complexity, Heuristics, and Experiments
| Autor: | de Col, Philipp, Klute, Fabian, N��llenburg, Martin |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: | |
| Popis: | 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 $\ell$. 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 \ge 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. Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|