Nearly Planar Graphs and {\lambda}-flat Graphs

Abstract : 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.
Type de document :
Pré-publication, Document de travail
2013
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00904543
Contributeur : Dimitrios M. Thilikos <>
Soumis le : jeudi 14 novembre 2013 - 16:23:17
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

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

Collections

Citation

Alexander Grigoriev, Athanassios Koutsonas, Dimitrios M. Thilikos. Nearly Planar Graphs and {\lambda}-flat Graphs. 2013. 〈lirmm-00904543〉

Partager

Métriques

Consultations de la notice

89