| Title: | Eliminating crossings in ordered graphs |
|---|
| Authors: | ID Agrawal, Akanksha (Author)
ID Cabello, Sergio (Author)
ID Kaufmann, Michael (Author)
ID Saurabh, Saket (Author)
ID Sharma, Roohani (Author)
ID Uno, Yushi (Author)
ID Wolff, Alexander (Author) |
|---|
| Files: |  PDF - Presentation file, download (1,13 MB)
MD5: 00CD0A665B319BC8393C2DD466730936
 URL - Source URL, visit https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.1
|
|---|
| Language: | English |
|---|
| Typology: | 1.08 - Published Scientific Conference Contribution |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | ordered graphs, book embedding, edge deletion, d-planar, hitting set |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Year of publishing: | 2024 |
|---|
| Number of pages: | 1:1-1:19 str. |
|---|
| PID: | 20.500.12556/DiRROS-20957  |
|---|
| UDC: | 519.17:004 |
|---|
| DOI: | 10.4230/LIPIcs.SWAT.2024.1 |
|---|
| COBISS.SI-ID: | 218342147 |
|---|
| Publication date in DiRROS: | 10.12.2024 |
|---|
| Views: | 47 |
|---|
| Downloads: | 27 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
