F. Klute, M. Nöllenburg:

"Minimizing Crossings In Constrained Two-Sided Circular Graph Layouts";

Journal of Computational Geometry,10(2019), 2; 45 - 69.

Circular graph layout is a popular drawing style, in which 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, which 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 its applicability.

http://dx.doi.org/10.20382/jocg.v10i2

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

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