Two-Sided Circular Layouts

Two-Sided Circular Layouts are an algorithmic technique for enhancing circular graph drawings by finding a set of edges to be drawn as curves in the outer face of the circle, significantly reducing interior edge crossings.

This work was presented at SoCG ‘18:

Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts
Fabian Klute and Martin Nöllenburg
34th International Symposium on Computational Geometry (SoCG 2018). DOI: 10.4230/LIPIcs.SoCG.2018.53

📊 Visual Comparison

From left to right:

1. Standard circular layout generated with OGDF.
2. Two-sided layout with crossing-free edges in the outer face ((k = 0)).
3. Two-sided layout with up to one crossing per edge in the outer face ((k = 1)).

💾 Code & Test Instances

• 📦 Download Source Code (two_sided.tar.gz)
  Includes a qmake project file. The easiest way to build and run the tool is using the QtCreator IDE.
• 🗂️ Download Benchmark Instances (instances.tar.gz)

📄 Abstract

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