Eliminating crossings in ordered graphs

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

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.

• Jezik: Angleški jezik
• Ključne besede: ordered graphs, book embedding, edge deletion, d-planar, hitting set
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.08 - Objavljeni znanstveni prispevek na konferenci
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Različica publikacije: Objavljena publikacija
• Leto izida: 2024
• Št. strani: 1:1-1:19 str.
• PID: 20.500.12556/RUL-165616
• UDK: 519.17:004
• DOI: 10.4230/LIPIcs.SWAT.2024.1
• COBISS.SI-ID: 218342147
• Datum objave v RUL: 10.12.2024

Gradivo je del monografije

• Naslov: 19th Scandinavian Symposium and Workshops on Algorithm Theory : SWAT 2024, June 12-14, 2024, Helsinki, Finland
• Uredniki: Hans L. Bodlaender
• Kraj izida: Saarbrücken/Wadern
• Založnik: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl Publishing
• Leto izida: 2024
• ISBN: 978-3-95977-318-8
• COBISS.SI-ID: 202480643
• Naslov zbirke: LIPIcs - Leibniz International Proceedings in Informatics
• Številčenje v zbirki: ǂvol. ǂ294
• ISSN zbirke: 1868-8969

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.