Min-$k$-planar Drawings of Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909098482597888 |
|---|---|
| author | Binucci, Carla Büngener, Aaron Di Battista, Giuseppe Didimo, Walter Dujmović, Vida Hong, Seok-Hee Kaufmann, Michael Liotta, Giuseppe Morin, Pat Tappini, Alessandra |
| author_facet | Binucci, Carla Büngener, Aaron Di Battista, Giuseppe Didimo, Walter Dujmović, Vida Hong, Seok-Hee Kaufmann, Michael Liotta, Giuseppe Morin, Pat Tappini, Alessandra |
| contents | The study of nonplanar drawings of graphs with restricted crossing configurations is a well-established topic in graph drawing, often referred to as beyond-planar graph drawing. One of the most studied types of drawings in this area are the $k$-planar drawings $(k \geq 1)$, where each edge cannot cross more than $k$ times. We generalize $k$-planar drawings, by introducing the new family of min-$k$-planar drawings. In a min-$k$-planar drawing edges can cross an arbitrary number of times, but for any two crossing edges, one of the two must have no more than $k$ crossings. We prove a general upper bound on the number of edges of min-$k$-planar drawings, a finer upper bound for $k=3$, and tight upper bounds for $k=1,2$. Also, we study the inclusion relations between min-$k$-planar graphs (i.e., graphs admitting min-$k$-planar drawings) and $k$-planar graphs. In our setting we only allow simple drawings, that is, any two edges cross at most once, no two adjacent edges cross, and no three edges intersect at a common crossing point. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_13401 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Min-$k$-planar Drawings of Graphs Binucci, Carla Büngener, Aaron Di Battista, Giuseppe Didimo, Walter Dujmović, Vida Hong, Seok-Hee Kaufmann, Michael Liotta, Giuseppe Morin, Pat Tappini, Alessandra Computational Geometry The study of nonplanar drawings of graphs with restricted crossing configurations is a well-established topic in graph drawing, often referred to as beyond-planar graph drawing. One of the most studied types of drawings in this area are the $k$-planar drawings $(k \geq 1)$, where each edge cannot cross more than $k$ times. We generalize $k$-planar drawings, by introducing the new family of min-$k$-planar drawings. In a min-$k$-planar drawing edges can cross an arbitrary number of times, but for any two crossing edges, one of the two must have no more than $k$ crossings. We prove a general upper bound on the number of edges of min-$k$-planar drawings, a finer upper bound for $k=3$, and tight upper bounds for $k=1,2$. Also, we study the inclusion relations between min-$k$-planar graphs (i.e., graphs admitting min-$k$-planar drawings) and $k$-planar graphs. In our setting we only allow simple drawings, that is, any two edges cross at most once, no two adjacent edges cross, and no three edges intersect at a common crossing point. |
| title | Min-$k$-planar Drawings of Graphs |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2308.13401 |