Profile and Neighborhood Complexity of Planar Graphs

Problem 41 · arXiv:2302.12633

arXiv Problem high confidence— first stated 2023-12-19

Authors: Gwenaël Joret, Clément Rambaud

Status open medium confidence

Problem 41 asks to determine the profile and neighborhood complexities of planar graphs up to a constant factor; as of 2026 the gaps (profile: $\Omega(r^3)$ vs $\mathcal{O}(r^4)$; neighborhood: $\Omega(r^2)$ vs $\mathcal{O}(r^4)$) remain unresolved for planar graphs. A 2025 follow-up (arXiv:2501.08895) improves bounds for graphs of bounded treewidth and graphs excluding a fixed minor, answering the related Problem 42 from the same paper, but planar graphs in general have unbounded treewidth and the specific planar-graph question of Problem 41 is not addressed by that work.

Cited literature (1)

partial Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs (2025)

Laurent Beaudou, Jan Bok, Florent Foucaud, Daniel A. Quiroz, Jean-Florent Raymond · arXiv preprint · arXiv:2501.08895

Improves profile and neighbourhood complexity bounds for graphs excluding a fixed minor and for graphs of bounded treewidth (answering Problem 42 of the source paper), but does not resolve the tight-bound question for general planar graphs (Problem 41).

Reviewer notes. The source paper was published in Combinatorica 44, 1115–1148 (2024). The 2025 follow-up arXiv:2501.08895 makes partial progress by answering Problem 42 (bounds for minor-free and bounded-treewidth graph classes), but Problem 41 for planar graphs specifically remains open. Note that planar graphs have unbounded treewidth (e.g., grid graphs), so bounded-treewidth results do not transfer directly to all planar graphs.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Determine the profile and neighborhood complexities of planar graphs up to a constant factor. For profile complexity, it is known to be in $\Omega(r^{3})$ (Theorem 36) and in $\operatorname{\mathcal{O}}(r^{4})$ (Theorem 2). For neighborhood complexity, it is known to be in $\Omega(r^{2})$ (Theorem 36 and Lemma 8) and in $\operatorname{\mathcal{O}}(r^{4})$ (Theorem 2).

Context

The paper closes with two open problems. The first asks for tight bounds on the profile and neighborhood complexities of planar graphs; the existing lower bounds ($\Omega(r^3)$ for profile, $\Omega(r^2)$ for neighborhood) and the paper's new upper bound ($\mathcal{O}(r^4)$ for both) leave a small gap that the authors consider tantalizingly close.

Source paper

Neighborhood complexity of planar graphs
Gwenaël Joret, Clément Rambaud · 2023-12-19
https://arxiv.org/abs/2302.12633