On balanced separators, treewidth, and cycle rank

DOI10.4310/JOC.2012.V3.N4.A5zbMATH Open1270.05063arXiv1012.1344OpenAlexW2963633500WikidataQ57424544 ScholiaQ57424544MaRDI QIDQ2375853FDOQ2375853

Hermann Gruber

Publication date: 25 June 2013

Published in: Journal of Combinatorics (Search for Journal in Brave)

Abstract: We investigate relations between different width parameters of graphs, in particular balanced separator number, treewidth, and cycle rank. Our main result states that a graph with balanced separator number k has treewidth at least k but cycle rank at most k(1 + log (n/k)), thus refining the previously known bounds, as stated by Robertson and Seymour (1986) and by Bodlaender et al. (1995). Furthermore, we show that the improved bounds are best possible.

Full work available at URL: https://arxiv.org/abs/1012.1344

zbMATH Keywords

bandwidthhypercubetreewidthpathwidthvertex rankingvertex separatorordered coloringcycle rank

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Connectivity (05C40)

Cited In (3)

• Balancing Bounded Treewidth Circuits
• Balancing bounded treewidth circuits
• Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes

This page was built for publication: On balanced separators, treewidth, and cycle rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2375853)