PhD Defense/Topology Seminar, Brett Smith (Wes): 'On Minimality of Planar Graphs with Respect to Treewdith'

Wednesday, April 15, 2015
4:15 PM - 5:30 PM (ET)
ESC 638
Event Type
Karen Collins,

Abstract: Robertson and Seymour developed the parameter, treewidth, in order to prove the Graph Minors Theorem, which says that the class of finite, undirected graphs is well-quasi-ordered by the minor relation. The treewidth of a graph can be defined using structures called brambles. A clique is a simple example of a bramble, but brambles can be much more intricate. The primary result in our work is a characterization of a family brambles in planar graphs, called 3-nets, along with an algorithm for determining the order of any bramble in this family. The 3-nets lead us to several results on the minimality of planar graphs with respect to tree width.

Get Directions
Event Date
Event Time