Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Dimitrios Thilikos Connect in order to contact the contributor
Submitted on : Monday, November 17, 2014 - 5:03:55 PM
Last modification on : Monday, October 11, 2021 - 1:24:07 PM
Long-term archiving on: : Friday, April 14, 2017 - 1:34:45 PM


mdcut ICGT 2014.pdf
Files produced by the author(s)


  • HAL Id : lirmm-01083698, version 1



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⟩



Record views


Files downloads