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 metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083698
Contributor : Dimitrios M. Thilikos <>
Submitted on : Monday, November 17, 2014 - 5:03:55 PM
Last modification on : Thursday, November 15, 2018 - 7:51:55 PM
Long-term archiving on : Friday, April 14, 2017 - 1:34:45 PM

File

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

Identifiers

  • 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. ⟨lirmm-01083698⟩

Share

Metrics

Record views

138

Files downloads

359