Bounds on half graph orders in powers of sparse graphs (Q2699651)

Summary: Half graphs and their variants, such as semi-ladders and co-matchings, are configurations that encode total orders in graphs. Works by \textit{H. Adler} and \textit{I. Adler} [Eur. J. Comb. 36, 322--330 (2014; Zbl 1284.05155)] and \textit{G. Fabiański} et al. [LIPIcs -- Leibniz Int. Proc. Inform. 126, Article 27, 16 p. (2019; Zbl 07559136)] prove that in powers of sparse graphs, one cannot find arbitrarily large configurations of this kind. However, these proofs either are non-constructive, or provide only loose upper bounds on the orders of half graphs and semi-ladders. In this work we provide nearly tight asymptotic lower and upper bounds on the maximum order of half graphs, parameterized by the power, in the following classes of sparse graphs: planar graphs, graphs with bounded maximum degree, graphs with bounded pathwidth or treewidth, and graphs excluding a fixed clique as a minor. The most significant part of our work is the upper bound for planar graphs. Here, we employ techniques of structural graph theory to analyze semi-ladders in planar graphs via the notion of cages, which expose a topological structure in semi-ladders. As an essential building block of this proof, we also state and prove a new structural result, yielding a fully polynomial bound on the neighborhood complexity in the class of planar graphs.