2026-07-22T18:58:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8766 2024-03-12T11:58:07Z ddc:004 open_access

Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts Klute, Fabian Nöllenburg, Martin Graph Drawing Circular Layouts Crossing Minimization Circle Graphs Bounded-Degree Maximum-Weight Induced Subgraphs 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 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 the applicability of our algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fabian Klute and Martin Nöllenburg 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.53 urn:nbn:de:0030-drops-87663 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.53 eng https://creativecommons.org/licenses/by/3.0/legalcode