Branch-width of planar graphs

each of which is associated with a certain way of decomposing
graphs. Bounded width implies a polynomial (often linear)
time algorithm for many combinatorial optimization problems
on graphs, typically through dynamic programming. The running
time of such algorithms depends exponentially on the width,
so it is important to determine the width of a given graph
accurately.

Unfortunately, the problem of deciding the width is NP-complete
in many cases, and it is the case for the branch-width of
general graphs. However, Seymour and Thomas (1994) proved
that the branch-width of a planar graph can be determined in
polynomial time.

In the first 30 minutes of this talk, I give a sketch of their
algorithm. In the remaining minutes, I will present a linear time
heuristic to compute a branch-decomposition of planar graphs,
which I have discovered recently, with some experimental results.
I will also briefly mention the application of this heuristic
to TSP solving.