We study the 1-planar, quasi-planar, and fan-planar crossing number in comparison to the (unrestricted) crossing number of graphs. We prove that there are n-vertex 1-planar (quasi-planar, fan-planar) graphs such that any 1-planar (quasi-planar, fan-planar) drawing has crossings, while O crossings suffice in a crossing-minimal drawing without restrictions on local edge crossing patterns.

Crossing Numbers of Beyond-Planar Graphs

Montecchiani F.;
2019

Abstract

We study the 1-planar, quasi-planar, and fan-planar crossing number in comparison to the (unrestricted) crossing number of graphs. We prove that there are n-vertex 1-planar (quasi-planar, fan-planar) graphs such that any 1-planar (quasi-planar, fan-planar) drawing has crossings, while O crossings suffice in a crossing-minimal drawing without restrictions on local edge crossing patterns.
2019
978-3-030-35801-3
978-3-030-35802-0
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/1457397
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 1
social impact