[Back]

F. Klute, M. Nöllenburg:
"Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts";
Talk: International Symposium on Computational Geometry (SoCG), Budapest; 2018-06-11 - 2018-06-14; in: "34th International Symposium on Computational Geometry", B. Speckmann, C. Tóth (ed.); LIPICS, Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, 99 (2018), ISBN: 978-3-95977-066-8; 53:1 - 53:14.

Circular layouts are a popular graph drawing style, where vertices are placed on a circle and edges are drawn as straight chords. Crossing minimization in circular layouts is NP-hard. One way to allow for fewer crossings in practice are two-sided layouts that draw some edges as curves in the exterior of the circle. In fact, one- and two-sided circular layouts are equivalent to one- page and two-page book drawings, i.e., graph layouts with all vertices placed on a line (the spine) and edges drawn in one or two distinct half-planes (the pages) bounded by the spine. In this paper we study the problem of minimizing the crossings for a fixed cyclic vertex order by computing an optimal k-plane set of exteriorly drawn edges for k ≥ 1, extending the previously studied case k = 0. We show that this relates to finding bounded-degree maximum-weight induced subgraphs of circle graphs, which is a graph-theoretic problem of independent interest. We show NP-hardness for arbitrary k, present an efficient algorithm for k = 1, and generalize it to an explicit XP-time algorithm for any fixed k. For the practically interesting case k = 1 we implemented our algorithm and present experimental results that confirm the applicability of our algorithm.

Graph Drawing, Circular Layouts, Crossing Minimization, Circle Graphs, Bounded-Degree Maximum-Weight Induced Subgraphs

http://dx.doi.org/10.4230/LIPIcs.SoCG.2018.53

http://drops.dagstuhl.de/opus/volltexte/2018/8766/pdf/LIPIcs-SoCG-2018-53.pdf