de Col, P., Klute, F., & Nöllenburg, M. (2019). Mixed Linear Layouts: Complexity, Heuristics, and Experiments. In Graph Drawing and Network Visualization. GD 2019 (pp. 460–467). Springer. https://doi.org/10.1007/978-3-030-35802-0_35
E192-01 - Forschungsbereich Algorithms and Complexity
-
Published in:
Graph Drawing and Network Visualization. GD 2019
-
Volume:
11904
-
Date (published):
2019
-
Event name:
International Symposium on Graph Drawing and Network Visualization (GD 2019)
-
Event date:
17-Sep-2019 - 20-Sep-2019
-
Event place:
Prag, Czechia
-
Number of Pages:
8
-
Publisher:
Springer, Cham
-
Peer reviewed:
Yes
-
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.
