Eliminating crossings in ordered graphs

Agrawal, Akanksha (author), Cabello, Sergio (author), Kaufmann, Michael (author), Saurabh, Saket (author), Sharma, Roohani (author), Uno, Yushi (author), Wolff, Alexander (author)

Drawing a graph in the plane with as few crossings as possible is one of the central problems in graph drawing and computational geometry. Another option is to remove the smallest number of vertices or edges such that the remaining graph can be drawn without crossings. We study both problems in a book-embedding setting for ordered graphs, that is, graphs with a fixed vertex order. In this setting, the vertices lie on a straight line, called the spine, in the given order, and each edge must be drawn on one of several pages of a book such that every edge has at most a fixed number of crossings. In book embeddings, there is another way to reduce or avoid crossings; namely by using more pages. The minimum number of pages needed to draw an ordered graph without any crossings is its (fixed-vertex-order) page number. We show that the page number of an ordered graph with $n$ vertices and $m$ edges can be computed in $2^m \cdot n^{{\mathcal O}(1)}$ time. An ${\mathcal O}(\log n)$-approximation of this number can be computed efficiently. We can decide in $2^{{\mathcal O}(d \sqrt{k} \log (d+k))} \cdot n^{{\mathcal O}(1)}$ time whether it suffices to delete $k$ edges of an ordered graph to obtain a $d$-planar layout (where every edge crosses at most $d$ other edges) on one page. As an additional parameter, we consider the size $h$ of a hitting set, that is, a set of points on the spine such that every edge, seen as an open interval, contains at least one of the points. For $h = 1$, we can efficiently compute the minimum number of edges whose deletion yields fixed-vertex-order page number $p$. For $h > 1$, we give an XP algorithm with respect to $h+p$. Finally, we consider spine+t-track drawings, where some but not all vertices lie on the spine. The vertex order on the spine is given; we must map every vertex that does not lie on the spine to one of $t$ tracks, each of which is a straight line on a separate page, parallel to the spine. In this setting, we can minimize in $2^n \cdot n^{{\mathcal O}(1)}$ time either the number of crossings or, if we disallow crossings, the number of tracks.

• Language: English
• Keywords: ordered graphs, book embedding, edge deletion, d-planar, hitting set
• Work type: Article
• Typology: 1.08 - Published Scientific Conference Contribution
• Organization: FMF - Faculty of Mathematics and Physics
• Publication version: Version of Record
• Year: 2024
• Number of pages: 1:1-1:19 str.
• PID: 20.500.12556/RUL-165616
• UDC: 519.17:004
• DOI: 10.4230/LIPIcs.SWAT.2024.1
• COBISS.SI-ID: 218342147
• Publication date in RUL: 10.12.2024

Record is a part of a monograph

• Title: 19th Scandinavian Symposium and Workshops on Algorithm Theory : SWAT 2024, June 12-14, 2024, Helsinki, Finland
• Editors: Hans L. Bodlaender
• Place of publishing: Saarbrücken/Wadern
• Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl Publishing
• Year: 2024
• ISBN: 978-3-95977-318-8
• COBISS.SI-ID: 202480643
• Collection title: LIPIcs - Leibniz International Proceedings in Informatics
• Collection numbering: ǂvol. ǂ294
• Collection ISSN: 1868-8969

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.