# Two Sided Circular Layouts

Two-Sided Circular Layouts are a technique of enhancing circular graph drawings by finding a set of edges, which is then to be drawn in the outer face. On this website you find the code and test data used in the paper Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts by Fabian Klute and Martin Nöllenburg, presented at SoCG'18 in Budapest.

The here displayed pictures show, from left to right, a circular layout generated with OGDF, a two-sided layout with crossing free edges in the outer face and a two-sided layout with up to one crossing per edge in the outer face. The code is available in the following archive:

and the instances under:

The code comes with a qmake project file. The easiest way to build it is to use the QtCreator IDE.

From the paper:

*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 \ge 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.