scientific article

zbMath0867.05069MaRDI QIDQ3128907

Satish B. Rao, Warren D. Smith, Serge A. Plotkin

Publication date: 3 August 1997

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

algorithmdecompositionseparatorsfinite element computationslimited-depth minor

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Well-mixing vertices and almost expanders ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Twin-width II: small classes ⋮ Small complete minors above the extremal edge density ⋮ Short proofs of some extremal results. II. ⋮ Efficient out-of-core algorithms for linear relaxation using blocking covers ⋮ Complete Minors in Graphs Without Sparse Cuts ⋮ Spectral partitioning works: planar graphs and finite element meshes ⋮ Harmless sets in sparse classes ⋮ 1-subdivisions, the fractional chromatic number and the Hall ratio ⋮ Combinatorial aspects of geometric graphs ⋮ Characterising graphs with no subdivision of a wheel of bounded diameter ⋮ Polynomial expansion and sublinear separators ⋮ Grid minors in damaged grids ⋮ On weighted sublinear separators ⋮ Sublinear separators, fragility and subexponential expansion ⋮ On low tree-depth decompositions ⋮ Grad and classes with bounded expansion. II: Algorithmic aspects ⋮ Non-existence of annular separators in geometric graphs ⋮ On nowhere dense graphs ⋮ Theory and application of width bounded geometric separators ⋮ Finding and Using Expanders in Locally Sparse Graphs ⋮ Sublinear time width-bounded separators and their application to the protein side-chain packing problem ⋮ A note on sublinear separators and expansion ⋮ Characterisations and examples of graph classes with bounded expansion ⋮ Testing outerplanarity of bounded degree graphs ⋮ New graph decompositions with applications to emulations ⋮ On classes of graphs with strongly sublinear separators ⋮ Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces ⋮ Notes on graph product structure theory ⋮ Approximating the maximum clique minor and some subgraph homeomorphism problems ⋮ Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs ⋮ The order of the largest complete minor in a random graph ⋮ Sublinear Separators in Intersection Graphs of Convex Shapes ⋮ Counting Homomorphisms to Sparse Graphs ⋮ Short and Simple Cycle Separators in Planar Graphs