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).