Geometric Extensions of Cutwidth in any Dimension - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2014

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.
Fichier principal
Vignette du fichier
mdcut ICGT 2014.pdf (274.28 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-01083698 , version 1 (17-11-2014)

Identifiers

  • HAL Id : lirmm-01083698 , version 1

Cite

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. ⟨lirmm-01083698⟩
106 View
218 Download

Share

Gmail Facebook X LinkedIn More