Boundary Classes of Planar Graphs
Vadim Lozin · Combinatorics Probability Computing · 2007
We analyse classes of planar graphs with respect to various properties such as polynomial-time solvability of thedominating setproblem or boundedness of the tree-width. A helpful tool to address this question is the notion of boundary classes. The main result of the paper is that for many important properties there are exactly two boundary classes of planar graphs.