Strongly Sublinear Separators and Polynomial Expansion

Abstract

A result of Plotkin, Rao, and Smith implies that graphs with polynomial expansion have strongly sublinear separators. We prove a converse of this result showing that hereditary classes of graphs with strongly sublinear separators have polynomial expansion.

This confirms a conjecture of the first author.

Keywords

• sublinear separators
• polynomial expansion