Edge-trewidth: Algorithmic and combinatorial properties - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Preprints, Working Papers, ... (Preprint) Year :

Edge-trewidth: Algorithmic and combinatorial properties

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 closed under 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 parametetrically 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.

Dates and versions

lirmm-03867242 , version 1 (23-11-2022)

Licence

Attribution

Identifiers

Cite

Loïc Magne, Christophe Paul, Abhijat Sharma, Dimitrios M. Thilikos. Edge-trewidth: Algorithmic and combinatorial properties. 2021. ⟨lirmm-03867242⟩
13 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More