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.
2017
9783319687049
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1427605
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 2
social impact