Crossing Numbers of Beyond-Planar Graphs Revisited

Onderzoeksoutput: Bijdrage aan congresAbstractAcademic

39 Downloads (Pure)


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.
Originele taal-2Engels
Aantal pagina's7
StatusGepubliceerd - 7 apr. 2021
Evenement37th European Workshop on Computational Geometry - Online, Saint Petersburg, Rusland
Duur: 7 apr. 20219 apr. 2021
Congresnummer: 37


Congres37th European Workshop on Computational Geometry
Verkorte titelEuroCG 2021
StadSaint Petersburg
Internet adres


Duik in de onderzoeksthema's van 'Crossing Numbers of Beyond-Planar Graphs Revisited'. Samen vormen ze een unieke vingerafdruk.

Citeer dit