Square roots of minor closed graph classes

DOI10.1016/j.dam.2013.05.026zbMath1285.05165OpenAlexW2083963621MaRDI QIDQ2442205

Dimitrios M. Thilikos, Nestor V. Nestoridis

Publication date: 2 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.05.026

zbMATH Keywords

graph minorsbranch-widthcarving-widthsquare roots of graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

An analysis of the parameterized complexity of periodic timetabling ⋮ A linear kernel for finding square roots of almost planar graphs ⋮ Computing square roots of graphs with low maximum degree ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ The Effect of Planarization on Width ⋮ Squares of low clique number ⋮ Finding cut-vertices in the square roots of a graph ⋮ Finding cactus roots in polynomial time ⋮ Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 ⋮ The Effect of Planarization on Width ⋮ Graph square roots of small distance from degree one graphs ⋮ Finding Cactus Roots in Polynomial Time

Cites Work

• Graph minors. XX: Wagner's conjecture
• Graph minors. V. Excluding a planar graph
• Graph minors. X: Obstructions to tree-decomposition
• Call routing and the ratcatcher
• Graph minors. XIII: The disjoint paths problem
• Graph minor theory
• Faster Parameterized Algorithms for Minor Containment
• Branch decompositions and minor containment
• Constructive linear time algorithms for branchwidth
• Algorithms for Square Roots of Graphs
• A criterion for planarity of the square of a graph