Klute, Fabian ;
Nöllenburg, Martin
Minimizing Crossings in Constrained TwoSided Circular Graph Layouts
Abstract
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 NPhard. One way to allow for fewer crossings in practice are twosided layouts that draw some edges as curves in the exterior of the circle. In fact, one and twosided circular layouts are equivalent to onepage and twopage book drawings, i.e., graph layouts with all vertices placed on a line (the spine) and edges drawn in one or two distinct halfplanes (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 kplane set of exteriorly drawn edges for k >= 1, extending the previously studied case k=0. We show that this relates to finding boundeddegree maximumweight induced subgraphs of circle graphs, which is a graphtheoretic problem of independent interest. We show NPhardness for arbitrary k, present an efficient algorithm for k=1, and generalize it to an explicit XPtime 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.
BibTeX  Entry
@InProceedings{klute_et_al:LIPIcs:2018:8766,
author = {Fabian Klute and Martin N{\"o}llenburg},
title = {{Minimizing Crossings in Constrained TwoSided Circular Graph Layouts}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {53:153:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770668},
ISSN = {18688969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8766},
URN = {urn:nbn:de:0030drops87663},
doi = {10.4230/LIPIcs.SoCG.2018.53},
annote = {Keywords: Graph Drawing, Circular Layouts, Crossing Minimization, Circle Graphs, BoundedDegree MaximumWeight Induced Subgraphs}
}
08.06.2018
Keywords: 

Graph Drawing, Circular Layouts, Crossing Minimization, Circle Graphs, BoundedDegree MaximumWeight Induced Subgraphs 
Seminar: 

34th International Symposium on Computational Geometry (SoCG 2018)

Issue date: 

2018 
Date of publication: 

08.06.2018 