Degeneracy Graphs

In some problems of the theory of convex polytopes one uses the possibility of representing a convex polytope as a(n) (undirected) graph1). Thus it is for example possible to reduce the problem of determining all vertices of a convex polytope to the problem of determining a spanning tree2) of the corresponding graph. Among other things, this approach is used in the procedures developed by MANAS/NEDOMA [1968] and DYER/PROLL [1977]. In their survey MATTHEIS/RUBIN [1980] call these procedures pivoting methods3). In case of degeneracy, however, the application of these procedures involves a considerable computational effort. This is due to the fact that a large-scale degeneracy of a convex polytope entails an increasing complexity of the corresponding graph (or certain subgraphs). This has been explained in particular by GAL [1978a] when dealing with the problem of determining all neighbouring vertices of a degenerate vertex of a convex polytope 4). In the above paper the structure of these special graphs (or subgraphs) is for the first time considered to be a theoretical object of investigation.