CS 269S, Winter 2012: Theory Seminar
Bren Hall, Room 1423
24 Feb 2012:

Approximate Tree Decompositions of Planar Graphs in Linear Time

Presenter: Jack Cheng

Frank Kammer and Torsten Tholey in SODA 2012

Abstract: An algorithm will be presented, that given a planar graph G with treewidth k on n vertices, computes a tree decomposition of width O(k) in time O(nk^3log k).