Nearly Planar Graphs and {\lambda}-flat Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2013

Nearly Planar Graphs and {\lambda}-flat Graphs

Résumé

A graph G is {\xi}-nearly planar if it can be embedded in the sphere so that each of its edges is crossed at most {\xi} times. The family of {\xi}-nearly planar graphs is widely extending the notion of planarity. We introduce an alternative parameterized graph family extending the notion of planarity, the {\lambda}-flat graphs, this time defined as powers of plane graphs in regard to a novel notion of distance, the wall-by-wall distance. We show that the two parameterized graph classes are parametrically equivalent.

Dates et versions

lirmm-00904543 , version 1 (14-11-2013)

Identifiants

  • HAL Id : lirmm-00904543 , version 1
  • ARXIV : 1311.0137

Citer

Alexander Grigoriev, Athanassios Koutsonas, Dimitrios M. Thilikos. Nearly Planar Graphs and {\lambda}-flat Graphs. 2013. ⟨lirmm-00904543⟩
120 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More