## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 40-54 |

Number of pages | 15 |

Journal | Discrete Applied Mathematics |

Volume | 341 |

DOIs | |

State | Published - Dec 31 2023 |

## Keywords

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

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics