Edge-trewidth: Algorithmic and combinatorial properties - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Pré-Publication, Document De Travail (Preprint/Prepublication) Année : 2021

Edge-trewidth: Algorithmic and combinatorial properties

Résumé

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 et versions

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

Licence

Paternité

Identifiants

Citer

Loïc Magne, Christophe Paul, Abhijat Sharma, Dimitrios M. Thilikos. Edge-trewidth: Algorithmic and combinatorial properties. 2021. ⟨lirmm-03867242⟩
18 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More