Planar induced paths via a decomposition into non-crossing ordered graphs

In any graph, the maximum size of an induced path is bounded by the maximum size of a path. However, in the general case, one cannot find a converse bound, even up to an arbitrary function, as evidenced by the case of cliques. Galvin, Rival and Sands proved in 1982 that, when restricted to weakly sparse graphs, such a converse property actually holds. In this paper, we consider the maximal function f such that any planar graph (and in general, any graph of bounded genus) containing a path on n vertices contains an induced path of size f (n), and prove that f (n) Θ (n n) by providing a lower bound matching the upper bound obtained by Esperet, Lemoine and Maffray, up to a constant factor. We obtain these tight bounds by analyzing graphs ordered along a Hamiltonian path that admit an edge partition into a bounded number of sets without crossing edges. In particular, we prove that when such an ordered graph can be partitioned into 2k sets of non-crossing edges, then it contains an induced path of size Ωₖ ( (n n) ^1/k) and provide almost matching upper bounds.