Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time
share
We consider decomposing a 3-connected planar graph G using laminar separators of size three. We show how to find a maximal set of laminar 3-separators in such a graph in linear time. We also discuss how to find maximal laminar set of 3-separators from special families. For example we discuss non-trivial cuts, ie. cuts which split G into two components of size at least two. For any vertex v, we also show how to find a maximal set of 3-separators disjoint from v which are laminar and satisfy: every vertex in a separator X has two neighbours not in the unique component of G-X containing v. In all cases, we show how to construct a corresponding tree decomposition of adhesion three. Our new algorithms form an important component of recent methods for finding disjoint paths in nonplanar graphs.
READ FULL TEXT