Geometric Extensions of Cutwidth in any Dimension
Résumé
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.
Domaines
Mathématique discrète [cs.DM]
Origine : Fichiers produits par l'(les) auteur(s)