Explicit bounds for graph minors

DOI10.1017/9781009093927.008zbMATH Open1391.05243arXiv1305.1451OpenAlexW2963559342WikidataQ130094756 ScholiaQ130094756MaRDI QIDQ723881FDOQ723881

R. B. Richter, Jim Geelen, Paul Wollan, Tony Huynh

Publication date: 24 July 2018

Published in: Journal of Combinatorial Theory. Series B, Surveys in Combinatorics 2022 (Search for Journal in Brave)

Abstract: Let $Sigma$ be a surface with boundary $b(Sigma)$, $mathcalL$ be a collection of $k$ disjoint $b(Sigma)$-paths in $Sigma$, and $P$ be a non-separating $b(Sigma)$-path in $Sigma$. We prove that there is a homeomorphism $phi:SigmaoSigma$ that fixes each point of $b(Sigma)$ and such that $phi(mathcalL)$ meets $P$ at most $2k$ times. With this theorem, we derive explicit constants in the graph minor algorithms of Robertson and Seymour. We reprove a result concerning redundant vertices for graphs on surfaces, but with explicit bounds. That is, we prove that there exists a computable integer $t:=t(Sigma,k)$ such that if $v$ is a '$t$-protected' vertex in a surface $Sigma$, then $v$ is redundant with respect to any $k$-linkage.

Full work available at URL: https://arxiv.org/abs/1305.1451

zbMATH Keywords

surfacesclique minorlinkagesminorsbranch sets

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph minors (05C83)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph minors. XX: Wagner's conjecture
• Graph minors. XIII: The disjoint paths problem
• Tight Bounds for Linkages in Planar Graphs
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Graph minors. XVI: Excluding a non-planar graph
• Graph minors. VII: Disjoint paths on a surface
• A simpler algorithm and shorter proof for the graph minor decomposition
• Untangling two systems of noncrossing curves
• Generating locally-cyclic triangulations of surfaces

Cited In (11)

• Explicit bounds for graph minors
• Low-dimensional topology. Abstracts from the workshop held January 15--21, 2023
• Short topological decompositions of non-orientable surfaces
• Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
• Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
• A lower bound on the tree-width of graphs with irrelevant vertices
• Explicit linear kernels for packing problems
• Shortest path embeddings of graphs on surfaces
• Discrete systolic inequalities and decompositions of triangulated surfaces
• A sharp bound for the growth of minimal graphs
• Title not available (Why is that?)

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Graph minor theory 👍 👎
• Minors in graphs of large girth 👍 👎
• Bounds on minimum semidefinite rank of graphs 👍 👎
• Upper Bounds on the Graph Minor Theorem 👍 👎
• On the extremal function for graph minors 👍 👎
• Explicit bounds for graph minors 👍 👎

This page was built for publication: Explicit bounds for graph minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q723881)