On the relationship between $k$-planar and $k$-quasi planar graphs

P. Angelini, M.A. Bekos, F.J. Brandenburg, G. Da Lozzo, G. Di Battista, W. Didimo, G. Liotta, F. Montecchiani, I. Rutter

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademic

69 Downloads (Pure)


A graph is $k$-planar $(k \geq 1)$ if it can be drawn in the plane such that no edge is crossed more than $k$ times. A graph is $k$-quasi planar $(k \geq 2)$ if it can be drawn in the plane with no $k$ pairwise crossing edges. The families of $k$-planar and $k$-quasi planar graphs have been widely studied in the literature, and several bounds have been proven on their edge density. Nonetheless, only trivial results are known about the relationship between these two graph families. In this paper we prove that, for $k \geq 3$, every $k$-planar graph is $(k+1)$-quasi planar.
Originele taal-2Engels
Pagina's (van-tot)1-17
StatusGepubliceerd - 28 feb 2017

Vingerafdruk Duik in de onderzoeksthema's van 'On the relationship between $k$-planar and $k$-quasi planar graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit