×

On the \(k\)-systems of a simple polytope. (English) Zbl 1009.52021

It is known that the combinatorial type of a simple polytope is determined by the isomorphism type of its edge graph \(G\) [R. Blind and P. Mani-Levitska, Aequationes Math. 34, 287-297 (1987; Zbl 0634.52005)]. Algorithms exist which perform this determination, however, the best known algorithms are exponential in the size of \(G\). The reader is referred to the work of G. Kalai [J. Comb. Theory, Ser. A 49, 381-383 (1988; Zbl 0673.05087)].
The article under review examines subproblems relating specifically to Kalai’s algorithm, with a view to finding polynomial-time solutions to them. The work is done in terms of \(k\)-systems. A \(k\)-system of \(P\) is a set of sets of vertices of \(P\) satisfying certain properties given in the article. An example is the set of vertex sets of the \(k\)-faces of \(P\), but other examples exist.
The article should be useful to anyone concerned to find efficient algorithms to characterize simple polytopes from their edge graphs.

MSC:

52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Achatz, H.; Kleinschmidt, P.; Kalai, G.; Ziegler, G. M., Reconstructing a simple polytope from its graph, Polytopes—Combinatorics and Computation, 155-165 (2000), Basel: Birkhäuser, Basel · Zbl 0967.52004
[2] Blind, R.; Mani-Levitska, P., On puzzles and polytope isomorphisms, Aequationes Mathematicae, 34, 287-297 (1987) · Zbl 0634.52005 · doi:10.1007/BF01830678
[3] M. Develin, e-mail conversation, Nov 2000, develin@bantha.org.
[4] Edmonds, J., Maximum matching and a polyhedron with 0,1-vertices, Journal of Research of the National Bureau of Standards-B (Mathematics and Mathematical Physics), 69B, 125-130 (1965) · Zbl 0141.21802
[5] Edmonds, J., Paths, trees, and flowers, Canadian Journal of Mathematics, 17, 449-467 (1965) · Zbl 0132.20903
[6] Ch. Haase and G. M. Ziegler,Examples and counterexamples for Perles’ conjecture, to appear in Discrete Computational Geometry. · Zbl 1011.52005
[7] Hammer, P. L.; Simeone, B.; Liebling, T. M.; de Werra, D., From linear separability to unimodality: A hierarchy of pseudo-boolean functions, SIAM Journal on Discrete Mathematics, 1, 174-184 (1988) · Zbl 0668.05061 · doi:10.1137/0401019
[8] Kalai, G., A simple way to tell a simple polytope from its graph, Journal of Combinatorial Theory, Series A, 49, 381-383 (1988) · Zbl 0673.05087 · doi:10.1016/0097-3165(88)90064-7
[9] Richter-Gebert, J., Realization Spaces of Polytopes (1996), Berlin: Springer, Berlin · Zbl 0866.52009
[10] Ziegler, G. M., Lectures on Polytopes (1995), New York: Springer-Verlag, New York · Zbl 0823.52002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.