A graph is k-planar (k≥ 1) if it can be drawn in the plane such that no edge is crossed k+ 1 times or more. A graph is k-quasi-planar (k≥ 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≥ 3, every k-planar graph is (k+ 1) -quasi-planar.
On the relationship between k-Planar and k-Quasi-planar graphs
Didimo, Walter;Liotta, Giuseppe;Montecchiani, Fabrizio;
2017
Abstract
A graph is k-planar (k≥ 1) if it can be drawn in the plane such that no edge is crossed k+ 1 times or more. A graph is k-quasi-planar (k≥ 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≥ 3, every k-planar graph is (k+ 1) -quasi-planar.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
