Degeneracy graphs and the neighbourhood problem (Q1072933)

This monograph deals with theory and applications of so-called degeneracy graphs being abstract representatives of degenerate vertices of convex polyhedra. In the first part (Chapter 1-4) the theory of degeneracy graphs is developed by introducing basic concepts and investigating structure and complexity of these special graphs. In the second part (Chapter 5) this theory is used for solving the so-called neighbourhood problems, i.e. the efficient determination of all neighbouring vertices of a degenerate vertex of interest. A solution method is proposed and its efficiency is tested.