Minimizing crossings in constrained two-sided circular graph layouts

DOI10.20382/JOCG.V10I2A4MaRDI QIDQ5207872zbMATH OpenOpenAlexFDO

Authors Fabian Klute, Martin Nöllenburg

Publication date 13 January 2020

Full work available at URL https://arxiv.org/abs/1803.05705

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

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 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 $kge1$, 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.

Recommendations

• scientific article; zbMATH DE number 7236457
• Graph-Theoretic Concepts in Computer Science
• Fixed-Location Circular Arc Drawing of Planar Graphs
• 1-page and 2-page drawings with bounded number of crossings per edge
• Approximating Crossing Minimization in Radial Layouts

Cited in

(7)

• scientific article; zbMATH DE number 7236457 (Why is no real title available?)
• Minimum-diameter cyclic arrangements in mapping data-flow graphs onto VLSI arrays
• Graph-Theoretic Concepts in Computer Science
• Treewidth, Circle Graphs, and Circular Drawings
• On circular layouts^∗
• Parameterized analysis and crossing minimization problems
• Crossing edge minimization in radial outerplanar layered graphs using segment paths

This page was built for publication: Minimizing crossings in constrained two-sided circular graph layouts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207872)