Vertex decompositions of two-dimensional complexes and graphs

MaRDI QIDQ5499938zbMATH OpenFDO

Authors Michał Adamaszek

Publication date 5 August 2015

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

zbMATH Keywords

complexitynonevasivenesssimplicial complexes

Mathematics Subject Classification ID

Combinatorial aspects of simplicial complexes (05E45) Combinatorial complexity of geometric structures (52C45) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We investigate families of two-dimensional simplicial complexes defined in terms of vertex decompositions. They include nonevasive complexes, strongly collapsible complexes of Barmak and Miniam and analogues of 2-trees of Harary and Palmer. We investigate the complexity of recognition problems for those families and some of their combinatorial properties. Certain results follow from analogous decomposition techniques for graphs. For example, we prove that it is NP-complete to decide if a graph can be reduced to a discrete graph by a sequence of removals of vertices of degree 3.

Recommendations

• Recognition of collapsible complexes is NP-complete
• Recognizing shrinkable complexes is NP-complete
• Recognizing shrinkable complexes is NP-complete
• Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
• A computationally intractable problem on simplicial complexes

Cited in

(4)

• A decomposition of 2-weak vertex-packing polytopes
• Systoles of 2-complexes, Reeb graph, and Grushko decomposition
• scientific article; zbMATH DE number 2103306 (Why is no real title available?)
• Combinatorial descriptions of multi-vertex 2-complexes

This page was built for publication: Vertex decompositions of two-dimensional complexes and graphs

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