Edge-treewidth: Algorithmic and combinatorial properties

Loïc Magne, Christophe Paul, Abhijat Sharma, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


We introduce the graph theoretical parameter of edge-treewidth. This parameter occurs in a natural way as the tree-like analogue of cutwidth or, alternatively, as an edge-analogue of treewidth. We study the combinatorial properties of edge-treewidth. We first observe that edge-treewidth does not enjoy any closeness properties under the known partial ordering relations on graphs. We introduce a variant of the topological minor relation, namely, the weak topological minor relation and we prove that edge-treewidth is monotone with respect to weak topological minors. Based on this new relation we are able to provide universal obstructions for edge-treewidth. The proofs are based on the fact that edge-treewidth of a graph is parametrically equivalent with the maximum over the treewidth and the maximum degree of the blocks of the graph. We also prove that deciding whether the edge-treewidth of a graph is at most k is an NP-complete problem.

Original languageEnglish (US)
Pages (from-to)40-54
Number of pages15
JournalDiscrete Applied Mathematics
StatePublished - Dec 31 2023


  • Edge-treewidth
  • Graph parameters
  • Obstructions
  • Treewidth
  • Weak topological minors

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Edge-treewidth: Algorithmic and combinatorial properties'. Together they form a unique fingerprint.

Cite this