P. de Col, F. Klute, M. Nöllenburg:

"Mixed Linear Layouts: Complexity, Heuristics, and Experiments";

Talk: International Symposium on Graph Drawing and Network Visualization (GD), Prag; 2019-09-17 - 2019-09-20; in: "GD 2019: Graph Drawing and Network Visualization", LNCS, 11904 (2019), ISBN: 978-3-030-35801-3; 460 - 467.

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.

http://dx.doi.org/10.1007/978-3-030-35802-0_35

https://publik.tuwien.ac.at/files/publik_284621.pdf

Created from the Publication Database of the Vienna University of Technology.