We investigate the product structure of hereditary graph classes admitting strongly sublinear separators. We characterise such classes as subgraphs of the strong product of a star and a complete graph of strongly sublinear size. In a more precise result, we show that if any hereditary graph class 𝒢 admits O(n 1-ϵ ) separators, then for any fixed δ∈(0,ϵ) every n-vertex graph in 𝒢 is a subgraph of the strong product of a graph H with bounded tree-depth and a complete graph of size O(n 1-ϵ+δ ). This result holds with δ=0 if we allow H to have tree-depth O(loglogn). Moreover, using extensions of classical isoperimetric inequalties for grids graphs, we show the dependence on δ in our results and the above td(H)∈O(loglogn) bound are both best possible. We prove that n-vertex graphs of bounded treewidth are subgraphs of the product of a graph with tree-depth t and a complete graph of size O(n 1/t ), which is best possible. Finally, we investigate the conjecture that for any hereditary graph class 𝒢 that admits O(n 1-ϵ ) separators, every n-vertex graph in 𝒢 is a subgraph of the strong product of a graph H with bounded tree-width and a complete graph of size O(n 1-ϵ ). We prove this for various classes 𝒢 of interest.
Dvořák et al. (Tue,) studied this question.