On balanced separators, treewidth, and cycle rank

DOI10.4310/JOC.2012.V3.N4.A5MaRDI QIDQ2375853zbMATH OpenOpenAlexWikidataFDO

Authors Hermann Gruber

Publication date 25 June 2013

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

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)

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.

Recommendations

• Treewidth of graphs with balanced separations
• Parameters tied to treewidth
• Treewidth for graphs with small chordality
• Rank-width and vertex-minors
• Safe separators for treewidth

Cited in

(4)

• Treewidth of graphs with balanced separations
• Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes
• Balancing Bounded Treewidth Circuits
• Balancing bounded treewidth circuits

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)