Geometric Extensions of Cutwidth in any Dimension

Abstract : We define a multi-dimensional geometric extension of cutwidth. A graph has d-cutwidth at most k if it can be embedded in the d-dimensional euclidean space so that no hyperplane can intersect more than k of its edges. We prove a series of combinatorial results on d-cutwidth which imply that for every d and k, there is a linear time algorithm checking whether the d-cutwidth of a graph G is at most k.
Type de document :
Communication dans un congrès
ICGT: International Colloquium on Graph Theory and Combinatorics, Jun 2014, Grenoble, France. 2014
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083698
Contributeur : Dimitrios M. Thilikos <>
Soumis le : lundi 17 novembre 2014 - 17:03:55
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : vendredi 14 avril 2017 - 13:34:45

Fichier

mdcut ICGT 2014.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01083698, version 1

Collections

Citation

Menelaos Karavelas, Dimitris Zoros, Spyridon Maniatis, Dimitrios M. Thilikos. Geometric Extensions of Cutwidth in any Dimension. ICGT: International Colloquium on Graph Theory and Combinatorics, Jun 2014, Grenoble, France. 2014. 〈lirmm-01083698〉

Partager

Métriques

Consultations de la notice

70

Téléchargements de fichiers

153