Faculty Recruiting Support CICS

Hedgewidth in Series-Parallel Graphs

30 Jan
Wednesday, 01/30/2019 12:15pm to 1:15pm
Computer Science Building Room 140
Theory Seminar
Speaker: Rik Sengupta

In structural graph theory, a powerful concept is that of a graph's "pathwidth" -- intuitively, how far it is from a path graph. A similar concept is that of a graph's "treewidth" -- how far it is from a tree. It is well known that the obstruction to bounded pathwidth is a large binary tree minor, while the obstruction to bounded treewidth is a large 2-connected planar graph minor (such as the 2-dimensional grid). It has been of some interest among graph theorists to explore whether there are any "intermediate" notions of width for which the obstruction set is an intermediate graph between a binary tree and a planar graph: a binary tree with an external vertex attached to it. In this talk, we answer this question in the case of series-parallel graphs, and make large strides towards proving it for general graphs. The intermediate notion of width turns out to be a surprisingly different one from the usual definitions of pathwidth and treewidth, and it involves an incredibly non-obvious structural aspect of certain graph embeddings: outerplanarity.

Faculty Host
: