arxiv: 2605.11112 · v1 · submitted 2026-05-11 · 🧮 math.CO · cs.DM

Recognition: 2 theorem links

· Lean Theorem

A coarse Menger's Theorem for planar and bounded genus graphs

Evangelos Protopapas, Micha{\l} Pilipczuk, V\'aclav Bla\v{z}ej

Pith reviewed 2026-05-13 02:27 UTC · model grok-4.3

classification 🧮 math.CO cs.DM

keywords Menger's theoremcoarse Menger theoremplanar graphsbounded genusgraph minorsS-T pathsdistance coveringcolorful graph minors

0 comments

The pith

In graphs embeddable on any fixed surface, the absence of k pairwise distance-(d+1) S-T paths implies a small vertex set X whose d-neighborhood intersects every S-T path.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a coarse analogue of Menger's theorem that holds for every surface Σ. In a Σ-embeddable graph with terminals S and T, if there are no k S-T paths that are pairwise more than d apart, then a set X of size at most f(d,k) exists such that every S-T path lies at distance at most d from some vertex of X. A reader would care because the result supplies a bounded modulator that reduces path-cover questions on planar and bounded-genus graphs to a small core, even though the same statement fails on general graphs.

Core claim

For every surface Σ there exists a function f:ℕ×ℕ→ℕ such that for every d,k and every Σ-embeddable graph G with terminals S,T, if G has no k pairwise distance-(d+1) S-T paths then there is a set X of at most f(d,k) vertices so that every S-T path lies at distance ≤d from X.

What carries the argument

The colorful graph-minor structure theorem applied to the annotated terminal sets S and T, which produces a bounded-size modulator for the distance-d covering property.

If this is right

The coarse Menger property holds uniformly across all graphs embeddable on any given surface.
The result supplies a partial positive answer to the questions of Nguyen, Scott, and Seymour concerning the existence of such coarse statements.
Colorful graph-minor structure theorems become a practical tool for obtaining distance-relaxed separators in surface-embedded graphs.
The same reduction to a small modulator applies to any algorithmic problem whose solution can be localized near a bounded set of vertices.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Because the modulator size depends only on d, k and the surface, the statement yields polynomial-time algorithms on surfaces whenever the localized problem on the modulator can be solved efficiently.
The same colorful-minor approach may extend coarse Menger-type statements to other minor-closed classes once analogous structure theorems are available.
Rapid growth of f(d,k) is expected from minor-theory bounds, yet the mere existence of a finite f already separates surfaces from general graphs.

Load-bearing premise

A structure theorem from colorful graph-minor theory supplies a bounded-size modulator that forces the distance-d covering property for the terminals S and T.

What would settle it

An explicit family of graphs embeddable on a fixed surface Σ, together with fixed d and k, in which the minimal size of any d-covering set X for S-T paths grows without bound while no k pairwise distance-(d+1) S-T paths exist.

Figures

Figures reproduced from arXiv: 2605.11112 by Evangelos Protopapas, Micha{\l} Pilipczuk, V\'aclav Bla\v{z}ej.

**Figure 2.** Figure 2: Elementary grid is used to create a (t × z)-elementary wall that has horizontal paths Pi and vertical paths Qj . Grids and walls are any subdivisions of elementary grids and walls. 8 [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

**Figure 3.** Figure 3: A graph G drawn on the sphere Σ and two families of closed disks in Σ. (a) This family is a Σ-rendition of G. (b) This family breaks every condition for being a Σ-rendition of G. (c) A D-aligned disk ∆, a D-grounded red cycle, and a D-grounded blue dotted path. Observe that every planar graph G has a trivial Σ-rendition where every vertex is a ground vertex and every edge belongs to its own cell with perip… view at source ↗

**Figure 5.** Figure 5: A (∆in , ∆out)-nest of order 5 sandwiched by a pair of D-aligned disks (Θin , Θout). Next, a (∆in , ∆out)-nest of order s ∈ N⩾2 is a sequence C = (C1, . . . , Cs) of pairwise disjoint cycles in G such that for every i ∈ [s], Ci bounds a disk ∆i in Σ in such a way that ∆in = ∆1 ⊆ ∆2 ⊆ . . . ⊆ ∆s = ∆out , see [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗

**Figure 6.** Figure 6: A (5 × 6)-wall segment [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗

**Figure 9.** Figure 9: A [PITH_FULL_IMAGE:figures/full_fig_p016_9.png] view at source ↗

**Figure 10.** Figure 10: Concatenation of W1, W2, and W3 [PITH_FULL_IMAGE:figures/full_fig_p016_10.png] view at source ↗

**Figure 11.** Figure 11: A (9, 11, 3, 5)-walloid 14 [PITH_FULL_IMAGE:figures/full_fig_p016_11.png] view at source ↗

**Figure 12.** Figure 12: Flap segment Wi of W of arity q = 3. Θin j Θout j [PITH_FULL_IMAGE:figures/full_fig_p018_12.png] view at source ↗

**Figure 14.** Figure 14: Considering R of Lemma 4.3, each set of cells is either entirely contained in the inner vortex disks (full red circles) or is c-represented by the walloid (empty blue squares). We note that the small set F of “forbidden” vertices featured in the statement of Lemma 4.3 will not be of relevance in the planar case, but will turn useful in the lift to the setting of graphs embeddable in more complicated surfa… view at source ↗

**Figure 15.** Figure 15: Obtaining a d-scattered S-T-linkage from a given d-scattered S-T-connector. Call two segments incident if they share an endpoint. We observe that non-incident segments are actually far from each other. Claim 1. For any two non-incident segments A, A′ , we have that {A, A′} is d-scattered in G. Proof. Suppose first that one of these segments is a subpath of some cycle of C; say A is the segment on Ci conne… view at source ↗

**Figure 16.** Figure 16: An illustration of how we obtain the (d,(C, R), X)-partial linkage Q in the proof of Lemma 6.3. Everything is set in place for the proof of the Combing Lemma. Recall that we have fixed in the context: a planar graph G, its Σ-rendition D, and the distance parameter d ∈ N. Lemma 6.3 (Combing Lemma). There exist functions f6.3, g6.3 : N 2 → N such that the following holds. Let k ∈ N. Suppose (C, R) is a rail… view at source ↗

**Figure 17.** Figure 17: A (6 × 4)-handle ssegment with its (first) exceptional path highlighted. Let x, respectively y, be the first left, respectively first right, boundary vertex of W1. We call the x-y-path P in W on the following set of edges {xv1, v1ut , utu ′ 1 , u′ 1 v ′ t , v′ tu1, u1vt , vtv ′ 1 , v′ 1u ′ t , u′ t y} the exceptional path of W. Moreover, notice that, assuming r ⩾ 5 and t ⩾ 6, W − V (P) contains an element… view at source ↗

**Figure 18.** Figure 18: A (6 × 6)-crosscap segment with its first and second exceptional path; the remaining (4 × 2)- crosscap segment along with the subpaths connecting its left/right boundary vertices to the original ones; all highlighted by different colors. Let x, respectively y, be the first left, respectively first right, boundary vertex of W1. We call the x-y-path P in W on the following set of edges {xv1, v1u1, u1v2t , v… view at source ↗

read the original abstract

Menger's Theorem is a fundamental result in graph theory. It states that if in a graph $G$ with distinguished sets of terminal vertices $S$ and $T$ there are no $k$ pairwise vertex-disjoint $S$-$T$ paths, then there is a set of less than $k$ vertices that intersects every $S$-$T$ path. In this work, we give a coarse variant of this result for planar and bounded genus graphs. Precisely, we prove that for every surface $\Sigma$ there is a function $f\colon \mathbb{N}\times \mathbb{N}\to \mathbb{N}$ such that for every pair of integers $d,k\in \mathbb{N}$ and a $\Sigma$-embeddable graph $G$ with distinguished sets of terminal vertices $S$ and $T$, if $G$ does not contain a family of $k$ $S$-$T$ paths that are pairwise at distance larger than $d$, then there is a set $X$ consisting of at most $f(d,k)$ vertices of $G$ such that every $S$-$T$ path is at distance at most $d$ from a vertex of $X$. This partially answers questions of Nguyen, Scott, and Seymour [arXiv:2508.14332], who proved that such a result cannot hold in general graphs. A key ingredient of our proof is a structure theorem from the developing ''colorful'' graph minor theory, where the focus is on studying the structure in a graph relative to some fixed subsets of annotated vertices. In our case, these annotated vertices are $S$ and $T$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a coarse Menger theorem for planar and bounded-genus graphs via colorful minors, where the general case fails.

read the letter

The paper shows that Menger's theorem has a coarse version on planar and bounded-genus graphs. No k S-T paths at pairwise distance greater than d implies a vertex set X of size f(d,k) that brings every S-T path within distance d of X. This is new. The authors cite the negative result for general graphs by Nguyen, Scott, and Seymour, and they get the positive result for surfaces by applying a colorful graph-minor structure theorem to the annotated terminals S and T. The paper does well by giving a precise statement and by using an existing tool from the literature rather than inventing new machinery. The approach fits the class of graphs where minor theory is strong. The main soft spot is whether the structure theorem produces a modulator with the exact distance-d covering property. It might give a small set whose deletion leaves no large minor or bounded treewidth, but paths could still wander far away. The proof must show how to get the uniform distance bound from that. The abstract points to this theorem as the key, so the details in the full paper need to confirm the extraction works without extra factors. The rest of the argument looks standard and free of circularity or hidden parameters. This paper is for graph theorists who work on structural results for planar graphs and connectivity problems. Readers looking for lemmas to use in algorithm design on surfaces would find it relevant. It deserves a serious referee. The claim is clear and the method is appropriate. I recommend putting it through peer review.

Referee Report

1 major / 2 minor

Summary. The paper proves a coarse Menger theorem for graphs embeddable on a fixed surface Σ: there exists a function f:ℕ×ℕ→ℕ such that, for any d,k and any Σ-embeddable G with terminals S,T, the absence of k pairwise distance-(d+1) S-T paths implies a vertex set X with |X|≤f(d,k) such that every S-T path lies at distance ≤d from X. The proof is built around an application of a colorful graph-minor structure theorem to the annotated pair (S,T).

Significance. The result is significant because it gives a positive answer for planar and bounded-genus graphs to a question for which Nguyen, Scott and Seymour already showed a negative answer in general graphs. The explicit use of colorful minor theory to obtain a bounded-size distance-d modulator is a technical strength; if the derivation is correct it supplies a clean structural statement that could seed further coarse variants inside minor-closed classes.

major comments (1)

[Proof of the main theorem (around the invocation of the colorful structure theorem)] The central step (application of the colorful structure theorem to produce the modulator X) must explicitly guarantee that every S-T path is at distance ≤d from X, not merely that G-X excludes a large S-T minor or has bounded treewidth. Please add a short paragraph immediately after the invocation of the structure theorem that extracts the metric covering property from the output of the theorem; without this extraction the bound f(d,k) does not follow.

minor comments (2)

[Abstract] The abstract states that the result 'partially answers' the questions of Nguyen et al.; a one-sentence clarification of which part of their question is settled and which remains open would help readers.
[Introduction] Notation for 'pairwise at distance larger than d' is used without an explicit definition in the first paragraph; add a short sentence defining the distance between two paths.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading, positive evaluation of the result's significance, and constructive suggestion for improving the clarity of the proof. We address the single major comment below and will make the requested revision.

read point-by-point responses

Referee: The central step (application of the colorful structure theorem to produce the modulator X) must explicitly guarantee that every S-T path is at distance ≤d from X, not merely that G-X excludes a large S-T minor or has bounded treewidth. Please add a short paragraph immediately after the invocation of the structure theorem that extracts the metric covering property from the output of the theorem; without this extraction the bound f(d,k) does not follow.

Authors: We agree that the manuscript would benefit from an explicit extraction step. While the colorful structure theorem (applied to the annotated pair (S,T)) yields a set X of size at most f(d,k) such that G-X contains no large colorful S-T minor, the metric covering property—that every S-T path lies within distance d of X—follows from the fact that a path avoiding the d-neighborhood of X could be combined with the planarity/bounded-genus embedding to produce additional pairwise distance-(d+1) paths, contradicting the hypothesis. We will insert a short clarifying paragraph immediately after the invocation of the structure theorem that spells out this implication and thereby makes the derivation of the function f(d,k) fully explicit. revision: yes

Circularity Check

0 steps flagged

No circularity: existence claim derived from external colorful minor structure theorem

full rationale

The paper proves an existence statement for a function f(d,k) that produces a bounded-size modulator X with the distance-d covering property for S-T paths. This rests on applying a cited structure theorem from colorful graph-minor theory to the annotated terminals S and T. No equation, definition, or step in the provided abstract reduces the claimed f or the modulator property to a fitted input, self-definition, or self-citation chain; the key ingredient is an independent external theorem whose output is taken as given. The derivation is therefore self-contained against the cited benchmark and exhibits none of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result depends on a structure theorem from colorful graph-minor theory whose precise statement is not reproduced here; no numerical parameters are fitted and no new entities are postulated in the abstract.

axioms (1)

domain assumption Existence of a structure theorem in colorful graph-minor theory that controls the neighborhood of annotated sets S and T in surface-embeddable graphs
Invoked as the key ingredient; the abstract does not restate the theorem, so its assumptions are inherited from the cited developing theory.

pith-pipeline@v0.9.0 · 5619 in / 1524 out tokens · 44450 ms · 2026-05-13T02:27:40.697818+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear
A key ingredient of our proof is a structure theorem from the developing 'colorful' graph minor theory... annotated vertices are S and T.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
if G does not contain a family of k S-T paths that are pairwise at distance larger than d, then there is a set X ... every S-T path is at distance at most d from a vertex of X

Reference graph

Works this paper leans on

53 extracted references · 53 canonical work pages · 2 internal anchors

[1]

Abrishami, J

T. Abrishami, J. Czyżewska, K. Kluk, M. Pilipczuk, M. Pilipczuk, and P. Rzążewski. On coarse tree decompositions and coarse balanced separators.ArXiv preprint, abs/2502.20182, 2025

work page arXiv 2025
[2]

Adler, S

I. Adler, S. G. Kolliopoulos, P. K. Krause, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. Irrelevant vertices for the planar disjoint paths problem.Journal of Combinatorial Theory, Series B, 122:815–843, 2017

work page 2017
[3]

Adler and P

I. Adler and P. K. Krause. A lower bound on the tree-width of graphs with irrelevant vertices.Journal of Combinatorial Theory, Series B, 137:126–136, 2019

work page 2019
[4]

J. Ahn, J. P. Gollin, T. Huynh, and O. Kwon. A coarse Erdős-Pósa theorem. In36th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, pages 3363–3381. SIAM, 2025

work page 2025
[5]

Albrechtsen and J

S. Albrechtsen and J. Davies. Counterexample to the conjectured coarse grid theorem.ArXiv preprint, abs/2508.15342, 2025

work page arXiv 2025
[6]

Albrechtsen, M

S. Albrechtsen, M. Distel, and A. Georgakopoulos. Excluding K2,t as a fat minor.ArXiv preprint, abs/2510.14644, 2025

work page arXiv 2025
[7]

Albrechtsen, M

S. Albrechtsen, M. Distel, and A. Georgakopoulos. Small counterexamples to the fat minor conjecture. ArXiv preprint, abs/2601.05761, 2026

work page arXiv 2026
[8]

Albrechtsen and M

S. Albrechtsen and M. Hamann. A coarse Halin Grid Theorem with applications to quasi-transitive, locally finite graphs.ArXiv preprint, abs/2507.12973, 2025. 65

work page arXiv 2025
[9]

Albrechtsen, T

S. Albrechtsen, T. Huynh, R. W. Jacobs, P. Knappe, and P. Wollan. A Menger-type theorem for two induced paths.SIAM Journal on Discrete Mathematics, 38(2):1438–1450, 2024

work page 2024
[10]

Albrechtsen, R

S. Albrechtsen, R. W. Jacobs, P. Knappe, and P. Wollan. A characterisation of graphs quasi-isometric toK 4-minor-free graphs.Combinatorica, 45(6):61, 2025

work page 2025
[11]

Berger and P

E. Berger and P. D. Seymour. Bounded-diameter tree-decompositions.Combinatorica, 44(3):659–674, 2024

work page 2024
[12]

Coarse Balanced Separators in Fat-Minor-Free Graphs

E. Bonnet, H. Le, M. Pilipczuk, and M. Pilipczuk. Coarse balanced separators in fat-minor-free graphs. ArXiv preprint, abs/2604.11318, 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026
[13]

Chang, J

H. Chang, J. Conroy, Z. Tan, and D. W. Zheng. O(1)-distortion planar emulators for string graphs. ArXiv preprint, abs/2510.21700, 2025

work page arXiv 2025
[14]

Chepoi, F

V. Chepoi, F. F. Dragan, I. Newman, Y. Rabinovich, and Y. Vaxès. Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs.Discrete Computational Geometry, 47(1):187–214, 2012

work page 2012
[15]

J. Davies. String graphs are quasi-isometric to planar graphs.ArXiv preprint, abs/2510.19602, 2025

work page arXiv 2025
[16]

Davies, M

J. Davies, M. Hatzel, and R. Hickingbotham. Quasi-isometries between graphs with variable edge lengths.ArXiv preprint, abs/2503.07448, 2025

work page arXiv 2025
[17]

Davies, R

J. Davies, R. Hickingbotham, F. Illingworth, and R. McCarty. Fat minors cannot be thinned (by quasi-isometries).ArXiv preprint, abs/2405.09383, 2024

work page arXiv 2024
[18]

M. Distel. An alternative characterisation of graphs quasi-isometric to graphs of bounded treewidth. ArXiv preprint, abs/2512.21946, 2025

work page arXiv 2025
[19]

Distel, U

M. Distel, U. Giocanti, J. Hodor, C. Legrand-Duchesne, and P. Micek. A coarse Gallai theorem.ArXiv preprint, abs/2601.18439, 2026

work page arXiv 2026
[20]

Esperet, H

L. Esperet, H. Gahlawat, and U. Giocanti. Coarse cops and robber in graphs and groups.ArXiv preprint, abs/2502.15571, 2025

work page arXiv 2025
[21]

Gartland, T

P. Gartland, T. Korhonen, and D. Lokshtanov. On induced versions of Menger’s theorem on sparse graphs.ArXiv preprint, abs/2309.08169, 2023

work page arXiv 2023
[22]

Gavoille and C

C. Gavoille and C. Hilaire. Minor-universal graph for graphs on surfaces.ArXiv preprint, abs/2305.06673, 2023

work page arXiv 2023
[23]

Georgakopoulos and P

A. Georgakopoulos and P. Papasoglu. Graph minors and metric spaces.Combinatorica, 45(3):33, 2025

work page 2025
[24]

P. A. Golovach, G. Stamoulis, and D. M. Thilikos. Combing a linkage in an annulus.SIAM Journal on Discrete Mathematics, 37(4):2332–2364, 2023. 66

work page 2023
[25]

P. A. Golovach, G. Stamoulis, and D. M. Thilikos. Model-checking for First-Order logic with disjoint paths predicates in proper minor-closed graph classes. In23rd ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, pages 3684–3699. SIAM, 2023

work page 2023
[26]

Gorsky, E

M. Gorsky, E. Protopapas, and S. Wiederrecht. Quickly excluding an annotated planar graph.ArXiv preprint, abs/2602.06516, 2026. To appear at ICALP 2026

work page arXiv 2026
[27]

Gorsky, M

M. Gorsky, M. T. Seweryn, and S. Wiederrecht. Polynomial bounds for the graph minor structure theorem. pages 1961–1978, 2025

work page 1961
[28]

Hatzel and M

M. Hatzel and M. Pilipczuk. On graphs coverable by chubby shortest paths. In51st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2025, volume 16124 ofLecture Notes in Computer Science, pages 244–257. Springer, 2025

work page 2025
[29]

Hendrey, S

K. Hendrey, S. Norin, R. Steiner, and J. Turcotte. On an induced version of Menger’s theorem.Electronic Journal of Combinatorics, 31(4), 2024

work page 2024
[30]

Hickingbotham

R. Hickingbotham. Graphs that are quasi-isometric to graphs with bounded treewidth.ArXiv preprint, abs/2501.10840, 2025

work page arXiv 2025
[31]

[Kur30] Kazimierz Kuratowski

K.-i. Kawarabayashi, R. Thomas, and P. Wollan. Quickly excluding a non-planar graph.ArXiv preprint, abs/2010.12397, 2020

work page arXiv 2010
[32]

C.-H. Liu. Coarse Menger property of quasi-minor excluded graphs and length spaces. Manuscript, 2026

work page 2026
[33]

K. Menger. Zur allgemeinen Kurventheorie.Fundamenta Mathematicae, 10(1):96–115, 1927

work page 1927
[34]

B. Mohar. Uniqueness and minimality of large face-width embeddings of graphs.Combinatorica, 15(4):541–556, 1995

work page 1995
[35]

Mohar and C

B. Mohar and C. Thomassen.Graphs on Surfaces. Johns Hopkins series in the mathematical sciences. Johns Hopkins University Press, 2001

work page 2001
[36]

Nguyen, A

T. Nguyen, A. Scott, and P. Seymour. Asymptotic structure. I. Coarse tree-width.ArXiv preprint, abs/2501.09839, 2025

work page arXiv 2025
[37]

Nguyen, A

T. Nguyen, A. Scott, and P. Seymour. Asymptotic structure. II. Path-width and additive quasi-isometry. ArXiv preprint, abs/2509.09031, 2025

work page arXiv 2025
[38]

Nguyen, A

T. Nguyen, A. Scott, and P. Seymour. Asymptotic structure. III. Excluding a fat tree.ArXiv preprint, abs/2509.09035, 2025

work page arXiv 2025
[39]

Nguyen, A

T. Nguyen, A. Scott, and P. Seymour. Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture.ArXiv preprint, abs/2508.14332, 2025

work page arXiv 2025
[40]

Nguyen, A

T. Nguyen, A. Scott, and P. Seymour. Asymptotic structure. V. The coarse Menger conjecture in bounded path-width.ArXiv preprint, abs/2509.08762, 2025. 67

work page arXiv 2025
[41]

Nguyen, A

T. Nguyen, A. Scott, and P. Seymour. Asymptotic structure. VI. Distant paths across a disc.ArXiv preprint, abs/2509.07174, 2025

work page arXiv 2025
[42]

Nguyen, A

T. Nguyen, A. D. Scott, and P. D. Seymour. A counterexample to the coarse Menger conjecture.Journal of Combinatorial Theory, Series B, 173:68–82, 2025

work page 2025
[43]

C. Paul, E. Protopapas, D. M. Thilikos, and S. Wiederrecht. Obstructions to Erdős-Pósa dualities for minors. In65th Annual Symposium on Foundations of Computer Science, FOCS 2024, pages 31–52. IEEE, 2024

work page 2024
[44]

C. Paul, E. Protopapas, D. M. Thilikos, and S. Wiederrecht. The local structure theorem for graph minors with finite index.ArXiv preprint, abs/2507.02769, 2025

work page arXiv 2025
[45]

Colorful Minors

E. Protopapas, D. M. Thilikos, and S. Wiederrecht. Colorful minors.ArXiv preprint, abs/2507.10467,

work page internal anchor Pith review Pith/arXiv arXiv
[46]

To appear at ICALP 2026

work page 2026
[47]

Robertson and P

N. Robertson and P. Seymour. Graph minors. XXI. Graphs with unique linkages.Journal of Combina- torial Theory, Series B, 99(3):583–616, 2009

work page 2009
[48]

Robertson and R

N. Robertson and R. P. Vitray. Embeddings of graphs with no short non contractible cycles. In H. P. E. Korte, L. Lovasz and A. Schrijver, editors,Algorithms and Combinatorics, volume 261, pages 293–328. 1990

work page 1990
[49]

P. D. Seymour and R. Thomas. Uniqueness of highly representative surface embeddings.Journal of Graph Theory, 23(4):337–349, 1996

work page 1996
[50]

R. Tarjan. Depth-first search and linear graph algorithms. In12th Annual Symposium on Switching and Automata Theory, SW AT 1971, pages 114–121, 1971

work page 1971
[51]

D. M. Thilikos and S. Wiederrecht. The graph minors structure theorem through bidimensionality. ArXiv preprint, abs/2306.01724, 2023

work page arXiv 2023
[52]

D. M. Thilikos and S. Wiederrecht. Excluding surfaces as minors in graphs.ArXiv preprint, abs/2601.19230, 2026

work page arXiv 2026
[53]

Thomassen

C. Thomassen. Embeddings of graphs with no short noncontractible cycles.Journal of Combinatorial Theory, Series B, 48(2):155–177, 1990. 68

work page 1990