Samenvatting
Graph drawing beyond planarity focuses on drawings of high visual quality for non-planar graphs
which are characterized by certain forbidden edge configurations. A natural criterion for the quality
of a drawing is the number of edge crossings. The question then arises whether beyond-planar
drawings have a significantly larger crossing number than unrestricted drawings. Chimani et al.
[GD’19] gave bounds for the ratio between the crossing number of three classes of beyond-planar
graphs and the unrestricted crossing number. In this paper we extend their results to the main
currently known classes of beyond-planar graphs characterized by forbidden edge configurations and
answer several of their open questions.
which are characterized by certain forbidden edge configurations. A natural criterion for the quality
of a drawing is the number of edge crossings. The question then arises whether beyond-planar
drawings have a significantly larger crossing number than unrestricted drawings. Chimani et al.
[GD’19] gave bounds for the ratio between the crossing number of three classes of beyond-planar
graphs and the unrestricted crossing number. In this paper we extend their results to the main
currently known classes of beyond-planar graphs characterized by forbidden edge configurations and
answer several of their open questions.
| Originele taal-2 | Engels |
|---|---|
| Pagina's | 36:1-36:7 |
| Aantal pagina's | 7 |
| Status | Gepubliceerd - 7 apr. 2021 |
| Evenement | 37th European Workshop on Computational Geometry - Online, Saint Petersburg, Rusland Duur: 7 apr. 2021 → 9 apr. 2021 Congresnummer: 37 http://eurocg21.spbu.ru/ |
Congres
| Congres | 37th European Workshop on Computational Geometry |
|---|---|
| Verkorte titel | EuroCG 2021 |
| Land/Regio | Rusland |
| Stad | Saint Petersburg |
| Periode | 7/04/21 → 9/04/21 |
| Internet adres |