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

Julien Duron, Hugo Jacob · 2025

Read Planar induced paths via a decomposition into non-crossing ordered graphs by Julien Duron, Hugo Jacob (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-17835.txt.

Introduction

Julien Duron and Hugo Jacob bound how long a clean path must hide inside a flat graph. Their 2025 paper works on planar graphs, which can be drawn with no crossed edges. A clean, or induced, path may use no extra edges between its points.

Past work by Galvin, Rival, and Sands showed a bound for sparse graphs, but flat graphs lacked a tight one. The pair split graph edges into few non-crossing sets along a main path. That split yields a bound that matches the best known upper bound, up to a fixed factor. The growth is slow: log of size, scaled down a step.

Catalog record

CREATORJulien Duron, Hugo Jacob
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-17835

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Planar induced paths via a decomposition into non-crossing ordered graphs Julien Duron, Hugo Jacob Abstract 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 f such that any planar graph (and in general, any graph of bounded genus) containing a path on n n vertices contains an induced path of size f ⁡ ( n ) f(n) , and prove that f ⁡ ( n ) ∈ Θ ⁡ ( log ⁡ n log ⁡ log ⁡ n ) f(n)\in\Theta\left(\frac{\log n}{\log\log n}\right) 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 2 ​ k 2k sets of non-crossing edges, then it contains an induced path of size Ω k ​ ( ( log ⁡ n log ⁡ log ⁡ n ) 1 / k ) \Omega_{k}\left(\left(\frac{\log n}{\log\log n}\right)^{1/k}\right) and provide almost matching upper bounds. 0 0 footnotetext: *The work of Julien Duron on this project is supported by the project BOBR that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 948057). 0 0 footnotetext: \dagger The work of Hugo Jacob on this project is supported by ANR GODASse ANR-24-CE48-4377. Acknowledgements. We thank Daniel Gonçalves for his involvement in the discussions which lead to this paper, for sharing his knowledge, and for his guidance. We also thank the organisers of the first workshop of ANR GODASse where we could meet and establish the first results. 1 Introduction This paper is dedicated to answering some questions related to the ‘guaranteed’ size of longest induced paths in graphs with sufficiently long paths. The first result on this topic, obtained by Galvin, Rival and Sands [ GRS82 ] , states that there is an unbounded function f such that any K_{t,t} -subgraph-free graph containing a path of size n contains an induced path of size f(n) . This was independently discovered later in [ ALR12 ] , and the bounds on the growth function f have been studied further in [ DER24 , DR24 , HMST24 , CDR25 ] . To the best of our knowledge, the current best lower bound f=\Omega(\frac{\log\log n}{\log\log\log n}) was obtained in [ HMST24 ] while an almost matching upper bound f=O(\log\log n\cdot\log\log\log n) was proven recently in [ CDR25 ] . Finding the good dependence function between the size of paths and induced paths can be extended to any class of graphs \mathcal{C} : what is the largest function f_{\mathcal{C}} such that any graph in \mathcal{C} containing a path on n vertices (as a subgraph) has to contain a path on f_{\mathcal{C}}(n) vertices as an induced subgraph. We refer the reader to [ DER24 ] for a survey of the know bounds. The special case of the class \mathcal{P} of planar graphs has been repeatedly studied in the literature [ AV00 , GLM16 , ELM17 , DER24 ] , with a best known lower bound of f_{\mathcal{P}}=\Omega(\sqrt{\log n}) and a best upper bound of f_{\mathcal{P}}=O(\log n/\log\log n) both obtained in [ ELM17 ] . We prove that f_{\mathcal{P}}=\Theta(\log n/\log\log n) , improving the lower bound to match the upper bound up to a (relatively small) constant factor. Our proofs provide tight bounds in the general case of bounded genus graphs. An important observation is that when \mathcal{C} is a hereditary class, that is a class closed by taking induced subgraphs, the function f_{\mathcal{C}} is equal to f_{\mathcal{C}^{\prime}} where \mathcal{C}^{\prime} denotes the class of graphs of \mathcal{C} containing a Hamiltonian path. In addition, as observed in [ DER24 ] , ordered graphs naturally arise from graphs containing a Hamiltonian path, by simply ordering the vertices along this path. In this paper, we will follow this line of work, and exhibit in particular induced paths that are increasing with respect to the order given to our graphs. Considering ordered graphs allows to make precise arguments for graph classes excluding some ordered subgraphs. A typical example of an ordered subgraph one could exclude is the crossing , that is four vertices a\prec b\prec c\prec d with the two edges ac and bd , see Figure 1 Note that an ordered graph excluding a crossing is in particular outerplanar. In [ DER24 ] it was proven that, for graphs avoiding a crossing along a Hamiltonian path, a tight lower bound of \frac{\log n}{2} on the size of increasing induced paths was obtained, recovering in particular the known lower bound on outerplanar graphs. To prove a tight bound on planar graphs, we introduce k -non-crossing graphs, that are ordered graphs for which there exists a partition the set of edges into k parts, none of which contains a crossing. This definition comes from the fact that finding long induced paths in planar graphs can be reduced to finding long induced paths in 2 -non-crossing graphs. One can note that such a partition provides a book embedding (see e.g. [ BETT98 ] ), however since the vertex ordering is already fixed by the Hamiltonian path, graphs admitting such a partition are way more restricted than graphs of stack number k (the analog of k -non-crossing when the ordering can be chosen). For example, consider the (increasing) path on vertex set [2n] , on which we add the edges between vertices i and i+n for i\in[n] . This (unordered) graph admits a book embedding on 2 pages, but if it is considered as an ordered graph with the natural order of [2n] , then it is not (n-1) -non-crossing. Given a k -non-crossing (ordered) graph G , one can easily prove that for any set \{v_{1},\dots,v_{k+1}\} of k+1 vertices, there exists a large interval I\subseteq V(G) of vertices and least one vertex v_{i} such that v_{i} is not adjacent to any vertex of I . Using the hypothesis that the size of induced paths is sufficiently small, we strengthen this property to work for sets of at most k vertices; see Lemma 3.3 and Lemma 4.2 . From that fact, we describe a procedure to grow a set of induced paths (or trees depending on k ) which ends only after a certain number of steps. The intuition behind this procedure is the following. Consider a set of k induced paths, but not mutually induced, each one of them having a marked endpoint denoted the root of the path. We furthermore assume the existence of some large interval I of vertices that is adjacent to all the roots, and non adjacent to the rest of the paths. From I , and using the fact that we

Read the complete text