pith. sign in

arxiv: 1907.05940 · v7 · submitted 2019-07-12 · 💻 cs.DS · math.CO

Finding irrelevant vertices in linear time on bounded-genus graphs

Petr A. Golovach , Stavros G. Kolliopoulos , Giannos Stamoulis , Dimitrios M. Thilikos This is my paper

Pith reviewed 2026-05-24 22:05 UTC · model grok-4.3

classification 💻 cs.DS math.CO
keywords irrelevant vertexbounded genustreewidthlinear timeparameterized algorithmssurface embedded graphsminor deletiondisjoint paths
0
0 comments X

The pith

A decomposition into tree-structured pieces lets one find all irrelevant vertices in linear time on bounded-genus graphs.

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

The paper presents a framework that, for any problem obeying the irrelevant-vertex property, identifies in linear time a linear-size set of vertices whose removal leaves a graph of bounded treewidth when the input is embedded on a surface of bounded genus. Prior methods could locate one such vertex in linear time but required a quadratic number of repetitions to reduce the whole graph. The new technique works by first breaking the embedded graph into a tree of bounded-treewidth subgraphs so that a vertex irrelevant for the global instance can be recognized from its local piece alone.

Core claim

Any surface-embedded graph of bounded genus can be decomposed in linear time into a tree-structured collection of bounded-treewidth subgraphs such that, for problems satisfying the irrelevant-vertex property, the task of locating globally irrelevant vertices reduces to independent local checks inside each piece; the union of the vertices found this way yields an equivalent instance of bounded treewidth.

What carries the argument

Tree-structured collection of bounded-treewidth subgraphs obtained from the surface embedding, inside which local detection of globally irrelevant vertices becomes possible.

If this is right

  • The (Induced) Minor Folio, (Induced) Disjoint Paths, and F-Minor-Deletion problems all admit linear-time algorithms on bounded-genus graphs via this framework.
  • Any parameterized problem whose solution set is preserved under removal of irrelevant vertices obtains a linear-time reduction to bounded treewidth on surfaces.
  • The quadratic bottleneck that arose from repeatedly locating single irrelevant vertices is eliminated for the entire class of such problems.

Where Pith is reading between the lines

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

  • The same tree-of-pieces idea may apply to other topological parameters such as apex number or crossing number once suitable local detection rules are supplied.
  • If the decomposition can be computed for graphs of bounded Euler genus plus a few additional vertices, the method would immediately cover apex-minor-free graphs as well.
  • The framework separates the topological part of the argument from the problem-specific part, so new problems need only supply a local irrelevance test rather than a full quadratic-time search.

Load-bearing premise

The problem in question must allow a vertex to be declared irrelevant by looking only at its local bounded-treewidth piece after the decomposition.

What would settle it

A bounded-genus graph and a problem obeying the irrelevant-vertex property for which the local checks inside the decomposition pieces miss at least one vertex whose removal would still reduce treewidth while preserving equivalence.

Figures

Figures reproduced from arXiv: 1907.05940 by Dimitrios M. Thilikos, Giannos Stamoulis, Petr A. Golovach, Stavros G. Kolliopoulos.

Figure 1
Figure 1. Figure 1: A railed nest W with 6 cycles (in black) and 4 paths (in blue) as a subgraph of a graph G. Apart from W, we depict only the vertex vin in purple and the terminals in red. Definition 2.1. An r-railed nest of G is the union W of a collection C = {C1, . . . , Cr} of pairwise vertex disjoint cycles of G and a collection P = {P1, . . . , Pr} of pairwise vertex-disjoint paths of G such that 1. for every i ∈ {1, … view at source ↗
Figure 2
Figure 2. Figure 2: Top: An example of a pair (G, uroot) and an illustration of the bags of the radial distance decomposition of it. Vertices/faces of the same color have the same radial distance from uroot in G. In this example, same colored faces that share an edge are attributed to the same bag of the radial distance decomposition. Also, vertices depicted with the same color and the same style belong to the same bag of the… view at source ↗
Figure 3
Figure 3. Figure 3: Left: Some part of the radial distance decomposition of a planar single-rooted graph. The nodes corresponding to vertex sets are depicted as orange squares and the nodes corresponding to sets of faces are depicted as blue disks. Each vertex-face edge corresponds to a same-color cycle of G. Right: The visualization of an embedding of Sliceh G(Ce) in a pseudo-disk Ψ where Ce is the bold blue cycle on the out… view at source ↗
Figure 4
Figure 4. Figure 4: An example of a S 2 -embedded graph G and a sequence C of 3 nested cycles in G. The outer/inner cycle is the one bounding the yellow/blue disk. Lemma 3.6. Let (T, t0, χ) be the radial distance decomposition of a rooted embedding (G, u). Let e = (v, f) and e ′ = (v ′ , f′ ) be two non-root vertex-face edges of T where v ′ is a descendant of f. If distT (v, v′ ) = 2r, for some integer r ≥ 1, then there is a … view at source ↗
Figure 5
Figure 5. Figure 5: A 9-wall. The subdivision vertices are depicted in [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The collection {C1, . . . , C6} is not laminar. However, it becomes laminar if we remove from it either C1 or C2. Also, {C2, . . . , C6} is not strongly laminar but it becomes strongly laminar if we remove from it C5 or C6. 4.2 Laminar stellations Let G be a S 2 -embedded graph and let C be a collection of cycles of G. We say that C is laminar if for every C, C′ ∈ C, if ∆ and ∆′ are open disks bounded by t… view at source ↗
Figure 7
Figure 7. Figure 7: The contractions in the proof of Lemma 4.5. the blue cycles are disjoint cycles of G1 and the red cycle is one of the cycles of G2 and they are all copies of cycles in C + in Q = G+□K1,4. These cycles are contracted to the fat blue and red vertices that play the roles of the new vertices vC , for each C ∈ C+, in G + C+ . Notice now that for each color i ∈ [4], the copies of the cycles in C + i inside Gi do… view at source ↗
Figure 8
Figure 8. Figure 8: An example of an S 2 -embedded graph G (its vertices are depicted as disk-shaped nodes) and a subgraph H of its radial graph RG, depicted in blue. The faces of G that correspond to vertices of H are also drawn as yellow regions. The set Z(H) consists of the magenta-colored disk-shaped vertices and the gray-colored square-shaped vertices; all vertices are vertices of the radial graph RG. The faces of G that… view at source ↗
read the original abstract

The irrelevant vertex technique provides a powerful tool for the design of parameterized algorithms for a wide variety of problems on graphs. A common characteristic of these problems, permitting the application of this technique on surface-embedded graphs, is the fact that every graph of large enough treewidth contains a vertex that is irrelevant, in the sense that its removal yields an equivalent instance of the problem. The straightforward application of this technique yields algorithms with running time that is quadratic in the size of the input graph. This running time is due to the fact that it takes linear time to detect one irrelevant vertex and the total number of irrelevant vertices to be detected is linear as well. Using advanced techniques, sub-quadratic algorithms have been designed for particular problems, even in general graphs. However, designing a general framework for linear-time algorithms has been open, even for the bounded-genus case. In this paper we introduce a general framework that enables finding in linear time an entire set of irrelevant vertices whose removal yields a bounded-treewidth graph, provided that the input graph has bounded genus. Our technique consists of decomposing any surface-embedded graph into a tree-structured collection of bounded-treewidth subgraphs where detecting globally irrelevant vertices can be done locally and independently. Our method is applicable to a wide variety of known graph containment or graph modification problems where the irrelevant vertex technique applies. Examples include the (Induced) Minor Folio problem, the (Induced) Disjoint Paths problem, and the $\mathcal{F}$-Minor-Deletion problem.

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.

Referee Report

1 major / 2 minor

Summary. The paper claims to introduce a general framework that finds in linear time an entire set of irrelevant vertices on bounded-genus graphs, whose removal produces a bounded-treewidth graph. The key technique is a decomposition of any surface-embedded graph into a tree-structured collection of bounded-treewidth subgraphs such that globally irrelevant vertices (for problems satisfying the irrelevant-vertex property) can be detected locally and independently. The framework is stated to apply to (Induced) Minor Folio, (Induced) Disjoint Paths, and F-Minor-Deletion.

Significance. If the local-to-global transfer holds, the result supplies a uniform linear-time method for an entire family of problems on bounded-genus graphs, replacing the quadratic-time bound obtained by repeated single-vertex detection. This is a concrete algorithmic improvement for surface-embedded instances and supplies a reusable decomposition primitive that later work on other surface problems could invoke.

major comments (1)
  1. [decomposition construction] The central claim rests on the assertion that the tree decomposition permits local detection of globally irrelevant vertices. The manuscript must contain an explicit argument (likely in the section describing the decomposition) showing that any vertex irrelevant inside its local bag remains irrelevant for the original instance even when solution paths or minors may cross tree edges; without that argument the linear-time guarantee does not follow.
minor comments (2)
  1. [Abstract] The abstract refers to 'advanced techniques' that already achieve sub-quadratic time for particular problems; adding the relevant citations would clarify the precise novelty of the new general framework.
  2. Notation for the tree decomposition (bags, adhesion sets, surface embeddings) should be introduced once with a single consistent diagram rather than piecemeal.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and the constructive suggestion regarding the decomposition. We address the major comment below.

read point-by-point responses

  1. Referee: The central claim rests on the assertion that the tree decomposition permits local detection of globally irrelevant vertices. The manuscript must contain an explicit argument (likely in the section describing the decomposition) showing that any vertex irrelevant inside its local bag remains irrelevant for the original instance even when solution paths or minors may cross tree edges; without that argument the linear-time guarantee does not follow.

    Authors: We agree that an explicit argument is required to rigorously justify why local irrelevance transfers to the global instance. In the revised manuscript we will add a dedicated lemma (placed immediately after the decomposition construction) that proves the following: if a vertex v is irrelevant inside its local bag B, then v remains irrelevant for the original instance. The proof proceeds by contradiction, using the tree structure to show that any solution (path, minor, or deletion set) that would use v can be rerouted or replaced inside the bounded-treewidth bags without crossing tree edges in a way that affects global equivalence; the argument relies only on the irrelevant-vertex property assumed for the target problems and on the fact that the decomposition is a tree of bags whose interfaces have bounded size. This addition will make the linear-time claim fully self-contained. revision: yes

Circularity Check

0 steps flagged

No circularity; framework applies established irrelevant-vertex property via new decomposition

full rationale

The paper presents a decomposition of bounded-genus graphs into a tree-structured collection of bounded-treewidth subgraphs, allowing local detection of globally irrelevant vertices. No equations, parameters, or reductions are shown that equate outputs to inputs by construction. The central technique builds on the pre-existing irrelevant-vertex property (every large-treewidth graph contains an irrelevant vertex) without self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations that reduce the claim to unverified prior work by the same authors. The derivation remains independent and self-contained against external benchmarks for the listed problems.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no explicit free parameters, axioms, or invented entities; the framework rests on the pre-existing irrelevant-vertex property and bounded-genus embedding assumptions already standard in the literature.

pith-pipeline@v0.9.0 · 5814 in / 1036 out tokens · 17638 ms · 2026-05-24T22:05:59.032639+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

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

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

79 extracted references · 79 canonical work pages · 1 internal anchor

  1. [1]

    Fomin, Ignasi Sau, and Dimitrios M

    Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, and Dimitrios M. Thilikos. Fast minor testing in planar graphs.Algorithmica, 64(1):69–84, 2012.doi:10.1007/S00453-011-9563-9. 15

    work page doi:10.1007/s00453-011-9563-9 2012

  2. [2]

    Computing excluded minors

    Isolde Adler, Martin Grohe, and Stephan Kreutzer. Computing excluded minors. InProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 641–650, 2008. URL: https://dl.acm.org/doi/10.5555/1347082.1347153. 1

    work page doi:10.5555/1347082.1347153 2008

  3. [3]

    Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M

    Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Irrelevant vertices for the planar disjoint paths problem.Journal of Combinatorial Theory, Series B, 122:815–843, 2017.doi:10.1016/j.jctb.2016.10.001. 1, 29

    work page doi:10.1016/j.jctb.2016.10.001 2017

  4. [4]

    Alowerboundonthetree-widthofgraphswithirrelevantvertices

    IsoldeAdlerandPhilippKlausKrause. Alowerboundonthetree-widthofgraphswithirrelevantvertices. Journal of Combinatorial Theory, Series B, 137:126–136, 2019.doi:10.1016/J.JCTB.2018.12.008. 1

    work page doi:10.1016/j.jctb.2018.12.008 2019

  5. [5]

    Easy problems for tree-decomposable graphs

    Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12(2):308–340, 1991.doi:10.1016/0196-6774(91)90006-K. 6

    work page doi:10.1016/0196-6774(91)90006-k 1991

  6. [6]

    Thilikos

    Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. I. general upper bounds.SIAM Journal on Discrete Mathematics, 34(3):1623–1648, 2020. doi: 10.1137/19M1287146. 29

    work page doi:10.1137/19m1287146 2020

  7. [7]

    Thilikos

    Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. IV. an optimal algorithm.SIAM Journal on Computing, 52(4):865–912, 2023.doi:10.1137/21M140482X. 1, 29

    work page doi:10.1137/21m140482x 2023

  8. [8]

    Some classes of graphs with bounded treewidth.Bulletin of the EATCS, 36:116–125,

    Hans Bodlaender. Some classes of graphs with bounded treewidth.Bulletin of the EATCS, 36:116–125,

    work page

  9. [9]

    Borie, R

    Richard B. Borie, R. Gary Parker, and Craig A. Tovey. Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families.Algorithmica, 7(5–6):555–581, 1992.doi:10.1007/BF01758777. 6

    work page doi:10.1007/bf01758777 1992

  10. [10]

    Graph isomorphism parameterized by elimination distance to bounded degree.Algorithmica, 75(2):363–382, 2016.doi:10.1007/s00453-015-0045-3

    Jannis Bulian and Anuj Dawar. Graph isomorphism parameterized by elimination distance to bounded degree.Algorithmica, 75(2):363–382, 2016.doi:10.1007/s00453-015-0045-3. 29

    work page doi:10.1007/s00453-015-0045-3 2016

  11. [11]

    Fixed-parameter tractable distances to sparse graph classes.Algorith- mica, 79(1):139–158, 2017.doi:10.1007/s00453-016-0235-7

    Jannis Bulian and Anuj Dawar. Fixed-parameter tractable distances to sparse graph classes.Algorith- mica, 79(1):139–158, 2017.doi:10.1007/s00453-016-0235-7. 29

    work page doi:10.1007/s00453-016-0235-7 2017

  12. [12]

    Algorithms for the edge-width of an embedded graph.Computational Geometry, 45(5):215–224, 2012.doi:10.1016/j.comgeo.2011.12

    Sergio Cabello, Éric Colin de Verdière, and Francis Lazarus. Algorithms for the edge-width of an embedded graph.Computational Geometry, 45(5):215–224, 2012.doi:10.1016/j.comgeo.2011.12

    work page doi:10.1016/j.comgeo.2011.12 2012

  13. [13]

    Papadimitriou

    Zhi-Zhong Chen, Michelangelo Grigni, and Christos H. Papadimitriou. Map graphs.Journal of the ACM, 49(2):127–138, 2002.doi:10.1145/506147.506148. 16

    work page doi:10.1145/506147.506148 2002

  14. [14]

    Parameterized algorithm for the disjoint path problem on planar graphs: Exponential ink2 and linear in n

    Kyungjin Cho, Eunjin Oh, and Seunghyeok Oh. Parameterized algorithm for the disjoint path problem on planar graphs: Exponential ink2 and linear in n. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), pages 3734–3758. SIAM, 2023.doi: 10.1137/1.9781611977554.ch144. 3, 7, 12, 13, 30

    work page doi:10.1137/1.9781611977554.ch144 2023

  15. [15]

    Towards tight(er) bounds for the excluded grid theorem.Journal of Combinatorial Theory, Series B, 146:219–265, 2021.doi:10.1016/J.JCTB.2020.09.010

    Julia Chuzhoy and Zihan Tan. Towards tight(er) bounds for the excluded grid theorem.Journal of Combinatorial Theory, Series B, 146:219–265, 2021.doi:10.1016/J.JCTB.2020.09.010. 15

    work page doi:10.1016/j.jctb.2020.09.010 2021

  16. [16]

    The monadic second-order logic of graphs

    Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Information and Computation, 85(1):12–75, 1990.doi:10.1016/0890-5401(90)90043-H. 6

    work page doi:10.1016/0890-5401(90)90043-h 1990

  17. [17]

    The monadic second-order logic of graphs III: tree-decompositions, minors and complexity issues.RAIRO - Theoretical Informatics and Applications, 26:257–286, 1992.doi:10

    Bruno Courcelle. The monadic second-order logic of graphs III: tree-decompositions, minors and complexity issues.RAIRO - Theoretical Informatics and Applications, 26:257–286, 1992.doi:10. 1051/ita/1992260302571. 6

    work page arXiv 1992

  18. [18]

    The expression of graph properties and graph transformations in monadic second- order logic

    Bruno Courcelle. The expression of graph properties and graph transformations in monadic second- order logic. InHandbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations, pages 313–400. World Scientific, 1997. 6

    work page 1997

  19. [19]

    Demaine and MohammadTaghi Hajiaghayi

    Erik D. Demaine and MohammadTaghi Hajiaghayi. Diameter and treewidth in minor-closed graph families, revisited.Algorithmica, 40(3):211–215, 2004.doi:10.1007/s00453-004-1106-1. 9

    work page doi:10.1007/s00453-004-1106-1 2004

  20. [20]

    Demaine, MohammadTaghi Hajiaghayi, and Ken ichi Kawarabayashi

    Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken ichi Kawarabayashi. Contraction decomposi- tion in H-minor-free graphs and algorithmic applications. InProceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pages 441–450. ACM, 2011.doi:10.1145/1993636.1993696. 11, 12, 27

    work page doi:10.1145/1993636.1993696 2011

  21. [21]

    Demaine, MohammadTaghi Hajiaghayi, and Dimitrios M

    Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. The bidimensional theory of bounded-genus graphs.SIAM Journal on Discrete Mathematics, 20(2):357–371, 2006. doi:10.1137/040616929. 6, 15

    work page doi:10.1137/040616929 2006

  22. [22]

    Diameter and treewidth in minor-closed graph families.Algorithmica, 27:275–291, 2000.doi:10.1007/s004530010020

    David Eppstein. Diameter and treewidth in minor-closed graph families.Algorithmica, 27:275–291, 2000.doi:10.1007/s004530010020. 9

    work page doi:10.1007/s004530010020 2000

  23. [23]

    Dynamic generators of topologically embedded graphs

    David Eppstein. Dynamic generators of topologically embedded graphs. InProceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 599–608. SIAM, 2003. URL: https://dl.acm.org/doi/10.5555/644108.644208. 25

    work page doi:10.5555/644108.644208 2003

  24. [24]

    Fellows, Jan Kratochvíl, Matthias Middendorf, and Frank Pfeiffer

    Michael R. Fellows, Jan Kratochvíl, Matthias Middendorf, and Frank Pfeiffer. The complexity of induced minors and related problems.Algorithmica, 13(3):266–282, 1995.doi:10.1007/BF01190507. 29

    work page doi:10.1007/bf01190507 1995

  25. [25]

    Fomin, Petr A

    Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Giannos Stamoulis. Computing paths of large rank in planar frameworks deterministically.SIAM Journal on Discrete Mathematics, 39(1):92–118, 2025.doi:10.1137/24M1632759. 1

    work page doi:10.1137/24m1632759 2025

  26. [26]

    Compound logics for modification problems.ACM Transactions on Computational Logic, 26(1):2:1–2:57, December

    FedorV.Fomin, PetrA.Golovach, IgnasiSau, GiannosStamoulis, andDimitriosM.Thilikos. Compound logics for modification problems.ACM Transactions on Computational Logic, 26(1):2:1–2:57, December

    work page

  27. [27]

    1, 2, 30

    Issue date: January 2025.doi:10.1145/3696451. 1, 2, 30

    work page doi:10.1145/3696451 2025

  28. [28]

    Fomin, Petr A

    Fedor V. Fomin, Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. An algorithmic meta-theorem for graph modification to planarity and FOL.ACM Transactions on Computation Theory, 14(3–4):1–29, 2022.doi:10.1145/3571278. 1, 30 32

    work page doi:10.1145/3571278 2022

  29. [29]

    Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi

    Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Hitting topological minors is FPT. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1317–1326, 2020.arXiv:1904.02944,doi:10.1145/3357713.3384318. 1

    work page doi:10.1145/3357713.3384318 2020

  30. [30]

    Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M

    Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Kernels for (connected) dominating set on graphs with excluded topological minors.ACM Transactions on Algorithms, 14(1):6:1–6:31, 2018.doi:10.1145/3155298. 1

    work page doi:10.1145/3155298 2018

  31. [31]

    Fomin and Dimitrios M

    Fedor V. Fomin and Dimitrios M. Thilikos. Dominating sets in planar graphs: Branch-width and exponential speed-up.SIAM Journal on Computing, 36(2):281–309, 2006. doi:10.1137/ S0097539702419649. 16

    work page 2006

  32. [32]

    (Almost-)optimal FPT algorithm and kernel for T-Cycle on planar graphs

    Harmender Gahlawat, Abhishek Rathod, and Meirav Zehavi. (Almost-)optimal FPT algorithm and kernel for T-Cycle on planar graphs. In52nd International Colloquium on Automata, Languages, and Programming (ICALP), volume 334 ofLIPIcs. Leibniz International Proceedings in Informatics, pages 82:1–82:18. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025.doi:1...

    work page doi:10.4230/lipics.icalp 2025

  33. [33]

    Geelen, R

    James F. Geelen, R. Bruce Richter, and Gelasio Salazar. Embedding grids in surfaces.European Journal of Combinatorics, 25(6):785–792, 2004.doi:10.1016/J.EJC.2003.07.007. 15

    work page doi:10.1016/j.ejc.2003.07.007 2004

  34. [34]

    Golovach, Marcin Kamiński, Spyridon Maniatis, and Dimitrios M

    Petr A. Golovach, Marcin Kamiński, Spyridon Maniatis, and Dimitrios M. Thilikos. The parameterized complexity of graph cyclability.SIAM Journal on Discrete Mathematics, 31(1):511–541, 2017.doi: 10.1137/141000014. 1

    work page doi:10.1137/141000014 2017

  35. [35]

    Golovach, Marcin Kamiński, Daniël Paulusma, and Dimitrios M

    Petr A. Golovach, Marcin Kamiński, Daniël Paulusma, and Dimitrios M. Thilikos. Induced packing of odd cycles in planar graphs.Theoretical Computer Science, 420:28–35, 2012.doi:10.1016/j.tcs. 2011.11.004. 1

    work page doi:10.1016/j.tcs 2012

  36. [36]

    Golovach, Giannos Stamoulis, and Dimitrios M

    Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. Combing a linkage in an annulus. SIAM Journal on Discrete Mathematics, 37(4):2332–2364, 2023.doi:10.1137/22M150914X. 1, 29

    work page doi:10.1137/22m150914x 2023

  37. [37]

    Golovach, Giannos Stamoulis, and Dimitrios M

    Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. Hitting topological minor models in planar graphs is fixed parameter tractable.ACM Transactions on Algorithms, 19(3):23:1–23:29, 2023. doi:10.1145/3583688. 1

    work page doi:10.1145/3583688 2023

  38. [38]

    Golovach, Giannos Stamoulis, and Dimitrios M

    Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. Model-checking for first-order logic with disjoint paths predicates in proper minor-closed graph classes. InProceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), pages 3684–3699. SIAM, 2023. doi:10.1137/1.9781611977554.ch141. 1, 2, 30

    work page doi:10.1137/1.9781611977554.ch141 2023

  39. [39]

    Quickly excluding an annotated planar graph, 2026.arXiv:2602.06516,doi:10.48550/arXiv.2602.06516

    Maximilian Gorsky, Evangelos Protopapas, and Sebastian Wiederrecht. Quickly excluding an annotated planar graph, 2026.arXiv:2602.06516,doi:10.48550/arXiv.2602.06516. 21

    work page doi:10.48550/arxiv.2602.06516 2026

  40. [40]

    2011 , isbn =

    Martin Grohe, Ken ichi Kawarabayashi, Dániel Marx, and Paul Wollan. Finding topological subgraphs is fixed-parameter tractable. InProceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pages 479–488. ACM, 2011.doi:10.1145/1993636.1993700. 1

    work page doi:10.1145/1993636.1993700 2011

  41. [41]

    Martin Grohe, Ken ichi Kawarabayashi, and Bruce A. Reed. A simple algorithm for the graph minor decomposition – logic meets structural graph theory. InProceedings of the 24th Annual ACM- SIAM Symposium on Discrete Algorithms (SODA), pages 414–431. SIAM, 2013.doi:10.1137/1. 9781611973105.30. 31

    work page doi:10.1137/1 2013

  42. [42]

    Robert Hickingbotham and David R. Wood. Structural properties of graph products.Journal of Graph Theory, 109(2):107–136, 2025.doi:10.1002/jgt.23023. 14 33

    work page doi:10.1002/jgt.23023 2025

  43. [43]

    Planarity allowing few error vertices in linear time

    Ken ichi Kawarabayashi. Planarity allowing few error vertices in linear time. InProceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 639–648, 2009. doi:10.1109/FOCS.2009.45. 2, 3

    work page doi:10.1109/focs.2009.45 2009

  44. [44]

    Algorithms for finding an induced cycle in planar graphs and bounded genus graphs

    Ken ichi Kawarabayashi and Yusuke Kobayashi. Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. InProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1146–1155. SIAM, 2009.doi:10.1137/1.9781611973068.124. 1, 29

    work page doi:10.1137/1.9781611973068.124 2009

  45. [45]

    Algorithms for finding an induced cycle in planar graphs.Combinatorica, 30(6):715–734, 2010.doi:10.1007/S00493-010-2499-X

    Ken ichi Kawarabayashi and Yusuke Kobayashi. Algorithms for finding an induced cycle in planar graphs.Combinatorica, 30(6):715–734, 2010.doi:10.1007/S00493-010-2499-X. 29

    work page doi:10.1007/s00493-010-2499-x 2010

  46. [46]

    The induced disjoint paths problem

    Ken ichi Kawarabayashi and Yusuke Kobayashi. A linear time algorithm for the induced disjoint paths problem in planar graphs.Journal of Computer and System Sciences, 78(2):670–680, 2012. Extended abstract appeared in IPCO 2008 under the title “The induced disjoint paths problem”. doi:10.1016/j.jcss.2011.10.004. 29

    work page doi:10.1016/j.jcss.2011.10.004 2012

  47. [47]

    The disjoint paths problem in quadratic time.Journal of Combinatorial Theory, Series B, 102(2):424–435, 2012.doi:10.1016/j.jctb.2011

    Ken ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed. The disjoint paths problem in quadratic time.Journal of Combinatorial Theory, Series B, 102(2):424–435, 2012.doi:10.1016/j.jctb.2011. 07.004. 2

    work page doi:10.1016/j.jctb.2011 2012

  48. [48]

    Linkless and flat embeddings in 3-space

    Ken ichi Kawarabayashi, Stephan Kreutzer, and Bojan Mohar. Linkless and flat embeddings in 3-space. Discrete & Computational Geometry, 47(4):731–755, 2012.doi:10.1007/s00454-012-9413-9. 1

    work page doi:10.1007/s00454-012-9413-9 2012

  49. [49]

    Ken ichi Kawarabayashi, Bojan Mohar, and Bruce A. Reed. A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 771–780, 2008.doi:10.1109/FOCS.2008.53. 2, 3

    work page doi:10.1109/focs.2008.53 2008

  50. [50]

    Ken ichi Kawarabayashi and Bruce A. Reed. Computing crossing number in linear time. InProceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 382–390. ACM, 2007. doi:10.1145/1250790.1250848. 1, 2

    work page doi:10.1145/1250790.1250848 2007

  51. [51]

    Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. A near-optimal planarization algorithm. InProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1802–1811. SIAM, 2014.doi:10.1137/1.9781611973402.130. 1

    work page doi:10.1137/1.9781611973402.130 2014

  52. [52]

    Bart M. P. Jansen, Marcin L. Pilipczuk, and Erik Jan van Leeuwen. A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs.SIAM Journal on Discrete Mathematics, 35(4):2387–2429, 2021.doi:10.1137/20M1353782. 3, 4, 7, 12, 13

    work page doi:10.1137/20m1353782 2021

  53. [53]

    Bart M. P. Jansen and Michał Włodarczyk. Lossy planarization: A constant-factor approximate kernelization for planar vertex deletion.SIAM Journal on Computing, 54(1):1–91, 2025.doi:10.1137/ 22M152058X. 3, 4, 7, 12, 21

    work page 2025

  54. [54]

    Thilikos

    Marcin Kamiński and Dimitrios M. Thilikos. Contraction checking in graphs on surfaces. InProceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 14 ofLIPIcs, pages 182–193, 2012.doi:10.4230/LIPIcs.STACS.2012.182. 1

    work page doi:10.4230/lipics.stacs.2012.182 2012

  55. [55]

    Deleting vertices to graphs of bounded genus.Algorithmica, 81(9):3655–3691, 2019.doi:10.1007/s00453-019-00592-7

    Tomasz Kociumaka and Marcin Pilipczuk. Deleting vertices to graphs of bounded genus.Algorithmica, 81(9):3655–3691, 2019.doi:10.1007/s00453-019-00592-7. 1

    work page doi:10.1007/s00453-019-00592-7 2019

  56. [56]

    IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    Tuukka Korhonen, Konrad Majewski, Wojciech Nadara, Michał Pilipczuk, and Marek Sokołowski. Dynamic treewidth. InProceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 1734–1744. IEEE, 2023.doi:10.1109/FOCS57990.2023.00105. 2 34

    work page doi:10.1109/focs57990.2023.00105 2023

  57. [57]

    Minor containment and disjoint paths in almost-linear time

    Tuukka Korhonen, Michał Pilipczuk, and Giannos Stamoulis. Minor containment and disjoint paths in almost-linear time. InProceedings of the 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 53–61, 2024.doi:10.1109/FOCS61266.2024.00014. 2, 3

    work page doi:10.1109/focs61266.2024.00014 2024

  58. [58]

    Crossing number in slightly superexponential time

    Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, Jie Xue, and Meirav Zehavi. Crossing number in slightly superexponential time. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1412–1424. SIAM, 2025. Extended abstract. doi:10.1137/1.9781611978322.44. 1

    work page doi:10.1137/1.9781611978322.44 2025

  59. [59]

    Obtaining a planar graph by vertex deletion.Algorithmica, 62(3–4):807–822, 2012.doi:10.1007/s00453-010-9484-z

    Dániel Marx and Ildikó Schlotter. Obtaining a planar graph by vertex deletion.Algorithmica, 62(3–4):807–822, 2012.doi:10.1007/s00453-010-9484-z. 1

    work page doi:10.1007/s00453-010-9484-z 2012

  60. [60]

    A single exponential bound for the redundant vertex Theorem on surfaces

    Frédéric Mazoit. A single exponential bound for the redundant vertex theorem on surfaces, 2013. arXiv:1309.7820. 29

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  61. [61]

    A linear time algorithm for embedding graphs in an arbitrary surface.SIAM Journal on Discrete Mathematics, 12(1):6–26, 1999.doi:10.1137/S089548019529248X

    Bojan Mohar. A linear time algorithm for embedding graphs in an arbitrary surface.SIAM Journal on Discrete Mathematics, 12(1):6–26, 1999.doi:10.1137/S089548019529248X. 2

    work page doi:10.1137/s089548019529248x 1999

  62. [62]

    Johns Hopkins Series in the Mathematical Sciences

    Bojan Mohar and Carsten Thomassen.Graphs on Surfaces. Johns Hopkins Series in the Mathematical Sciences. Johns Hopkins University Press, 2001. URL:https://jhupbooks.press.jhu.edu/title/ graphs-surfaces. 4

    work page 2001

  63. [63]

    Thilikos

    Laure Morelle, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Faster parameterized algorithms for modification problems to minor-closed classes.TheoretiCS, 3, 2024.doi:10.46298/ THEORETICS.24.19. 1, 29, 30

    work page 2024

  64. [64]

    Bruce A. Reed. Rooted routing in the plane.Discrete Applied Mathematics, 57(2–3):213–227, 1995. doi:10.1016/0166-218X(94)00104-L. 2, 3, 7, 29

    work page doi:10.1016/0166-218x(94)00104-l 1995

  65. [65]

    Reed, Neil Robertson, Alexander Schrijver, and Paul D

    Bruce A. Reed, Neil Robertson, Alexander Schrijver, and Paul D. Seymour. Finding disjoint trees in planar graphs in linear time. In Neil Robertson and Paul D. Seymour, editors,Graph Structure Theory, volume 147 ofContemporary Mathematics, pages 295–301. American Mathematical Society, 1991. 2, 3, 29

    work page 1991

  66. [66]

    Graph minors

    Neil Robertson and Paul Seymour. Graph minors. XXI. graphs with unique linkages.Journal of Combinatorial Theory, Series B, 99(3):583–616, 2009.doi:10.1016/j.jctb.2008.08.003. 1

    work page doi:10.1016/j.jctb.2008.08.003 2009

  67. [67]

    Graph minors

    Neil Robertson and Paul Seymour. Graph minors. XXII. irrelevant vertices in linkage problems.Journal of Combinatorial Theory, Series B, 102(2):530–563, 2012.doi:10.1016/j.jctb.2007.12.007. 1

    work page doi:10.1016/j.jctb.2007.12.007 2012

  68. [68]

    Neil Robertson and Paul D. Seymour. Graph minors. III. planar tree-width.Journal of Combinatorial Theory, Series B, 36(1):49–64, 1984.doi:10.1016/0095-8956(84)90013-3. 4, 15

    work page doi:10.1016/0095-8956(84)90013-3 1984

  69. [69]

    Neil Robertson and Paul D. Seymour. Graph minors. X. obstructions to tree-decomposition.Journal of Combinatorial Theory, Series B, 52(2):153–190, 1991.doi:10.1016/0095-8956(91)90061-N. 16

    work page doi:10.1016/0095-8956(91)90061-n 1991

  70. [70]

    Neil Robertson and Paul D. Seymour. Graph minors. XIII. the disjoint paths problem.Journal of Combinatorial Theory, Series B, 63(1):65–110, 1995.doi:10.1006/jctb.1995.1006. 1, 2

    work page doi:10.1006/jctb.1995.1006 1995

  71. [71]

    Neil Robertson and Paul D. Seymour. Graph minors. XVI. excluding a non-planar graph.Journal of Combinatorial Theory, Series B, 89(1):43–76, 2003.doi:10.1016/S0095-8956(03)00042-X. 31

    work page doi:10.1016/s0095-8956(03)00042-x 2003

  72. [72]

    Seymour, and Robin Thomas

    Neil Robertson, Paul D. Seymour, and Robin Thomas. Quickly excluding a planar graph.Journal of Combinatorial Theory, Series B, 62(2):323–348, 1994.doi:10.1006/jctb.1994.1073. 15

    work page doi:10.1006/jctb.1994.1073 1994

  73. [73]

    Thilikos.Parameterizing the quantification of CMSO: model checking on minor-closed graph classes, pages 3728–3742.doi:10.1137/1.9781611978322.124

    Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos.Parameterizing the quantification of CMSO: model checking on minor-closed graph classes, pages 3728–3742.doi:10.1137/1.9781611978322.124. 1, 2, 30 35

    work page doi:10.1137/1.9781611978322.124

  74. [74]

    Thilikos.k-apices of minor-closed graph classes

    Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos.k-apices of minor-closed graph classes. II. parameterized algorithms.ACM Transactions on Algorithms, 18(3):21:1–21:30, 2022.doi:10.1145/ 3519028. 1

    work page 2022

  75. [75]

    An FPT-Algorithm for Recognizingk-Apices of Minor-Closed Graph Classes

    Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos.k-apices of minor-closed graph classes. II. parameterized algorithms.ACM Transactions on Algorithms, 18(3):21:1–21:30, 2022. Journal version of the ICALP 2020 paper “An FPT-Algorithm for Recognizingk-Apices of Minor-Closed Graph Classes”. doi:10.1145/3519028. 29

    work page doi:10.1145/3519028 2022

  76. [76]

    Thilikos.k-apices of minor-closed graph classes

    Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos.k-apices of minor-closed graph classes. I. bounding the obstructions.Journal of Combinatorial Theory, Series B, 161:180–227, 2023.doi: 10.1016/j.jctb.2023.02.012. 29, 30

    work page doi:10.1016/j.jctb.2023.02.012 2023

  77. [77]

    Thilikos, and Alexandre Vigny

    Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M. Thilikos, and Alexandre Vigny. Model checking disjoint-paths logic on topological-minor-free graph classes. InProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 68:1–68:12. ACM, 2024.doi:10.1145/3661814.3662089. 1, 30

    work page doi:10.1145/3661814.3662089 2024

  78. [78]

    IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    Michał Włodarczyk and Meirav Zehavi. Planar disjoint paths, treewidth, and kernels. InProceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2023), pages 649–662. IEEE, 2023.arXiv:2307.06792,doi:10.1109/FOCS57990.2023.00044. 3, 7, 12, 13, 21, 30

    work page doi:10.1109/focs57990.2023.00044 2023

  79. [79]

    Bodlaender, Babette de Fluiter, and Dimitrios M

    Koichi Yamazaki, Hans L. Bodlaender, Babette de Fluiter, and Dimitrios M. Thilikos. Isomorphism for graphs of bounded distance width.Algorithmica, 24(2):105–127, 1999.doi:10.1007/PL00009273. 12 36 A Appendix. Proof of Lemma 3.3 In the proof of Lemma 3.3 we will use the fact that there is a exactly one root edge in the tree of the radial distance decomposi...

    work page doi:10.1007/pl00009273 1999