On Balanced Separators, Treewidth, and Cycle Rank

Details On Balanced Separators, Treewidth, and Cycle Rank On Balanced Separators, Treewidth, and Cycle Rank

2010-12-06

arxiv.org/abs/1012.1344v1

Computer Science

Discrete Mathematics

Scientific paper

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. Among other results, we also determine the cycle rank of powers of path graphs, thus answering a question recently raised by Novotny et al. (2009).

Affiliated with

Also associated with

No associations

Rating

On Balanced Separators, Treewidth, and Cycle Rank does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Balanced Separators, Treewidth, and Cycle Rank, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Balanced Separators, Treewidth, and Cycle Rank will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-479320