2025/12/03 by Corentin Lunel, Clément Maria, Lunel, Corentin +1
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Geometric Topology (math.GT) #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2512.04074
openalex publication_date 2025/12/03 · openalex created_date 2025/12/05 · openalex updated_date 2026/07/28
The central theorem of topological graph theory states that the graph minor relation is a well-quasi-order on graphs. It has far-reaching consequences, in particular in the study of graph structures and the design of (parameterized) algorithms. In this article, we study two embedded versions of classical minor relations from structural graph theory and prove that they are also well-quasi-orders on general or restricted classes of embedded planar graphs. These embedded minor relations appear naturally for intrinsically embedded objects, such as knot diagrams and surfaces in ℝ3. Handling the extra topological constraints of the embeddings requires careful analysis and extensions of classical methods for the more constrained embedded minor relations. We prove that the embedded version of immersion induces a well-quasi-order on bounded carving-width plane graphs by exhibiting particularly well-structured tree-decompositions and leveraging a classical argument on well-quasi-orders on forests. We deduce that the embedded graph minor relation defines a well-quasi-order on plane graphs via their directed medial graphs, when their branch-width is bounded. We conclude that the embedded graph minor relation is a well-quasi-order on all plane graphs, using classical grids theorems in the unbounded branch-width case.