Special Seminar

Title: Bounding treewidth of planar graphs using three-sided brambles
Speaker: Brett Smith
Speaker Info: Yale University
Brief Description:
Special Note:

We discuss a method of organizing a network called a tree decomposition. A tree decomposition provides a natural way of searching through all connections in the network, and the maximum number of vertices used at any step of this search is called the width of the tree decomposition. Thus, a "good" tree decomposition will have a small width. The minimum width among all tree decompositions is called the treewidth of the graph. Treewidth lies at the heart of Roberson and Seymour's seminal work on Graph Minors.

We describe a polynomial-time algorithm for planar graphs that does two things: (1) constructs a tree decomposition of the graph, (2) finds an obstruction for any possible tree decomposition of the graph. Our algorithm results in both upper and lower bounds that are within a constant factor of the treewidth.

Date: Friday, February 02, 2018
Time: 3:00pm
Where: Lunt 107
Contact Person: Ben Weinkove
Contact email: weinkove@math.northwestern.edu
Contact Phone:
Copyright © 1997-2024 Department of Mathematics, Northwestern University.