Title: Bounding treewidth of planar graphs using three-sided brambles
Speaker: Brett Smith
Speaker Info: Yale University
Brief Description:
Special Note:
Abstract:
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.Date: Friday, February 02, 2018We 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.