References

 [1]

D. AVIS, D. BREMNER, AND R. SEIDEL, How good are convex hull algorithms?, Comput. Geom., Vol. 7, No. 5-6, pp. 265-301, 1997.

 [2]

D. AVIS AND K. FUKUDA, A pivoting algorithm for convex hull and vertex enumeration of arrangements and polyhedra, Discrete Comput. Geom., Vol. 8, No. 3, pp. 295-313, 1992.

 [3]

L. BABAI, Automorphism groups, isomorphism, reconstruction, in Handbook of Combinatorics, R. L. Graham, M. Grötschel, and L. Lovász, eds., Vol. 2, Elsevier (North-Holland), Amsterdam, 1995, pp. 1447-1540.

 [4]

A. BELOW, J. A. DE LOERA, AND J. RICHTER-GEBERT, The complexity of finding small triangulations of convex 3-polytopes. Journal of Algorithms, to appear; arXiv:math.CO/0012177, 2000.

 [5]

-------, Finding minimal triangulations of convex 3-polytopes is NP-hard, in Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms, San Francisco, CA, USA, SIAM, Philadelphia, pp. 65-66, 2000.

 [6]

R. BLIND AND P. MANI-LEVITSKA, On puzzles and polytope isomorphisms, Aequationes Math., Vol. 34, pp. 287-297, 1987.

 [7]

J. BOKOWSKI AND B. STURMFELS, Computational Synthetic Geometry, No. 1355 in Lecture Notes in Mathematics, Springer-Verlag, 1989.

 [8]

D. BREMNER, K. FUKUDA, AND A. MARZETTA, Primal-dual methods for vertex and facet enumeration, Discrete Comput. Geom., Vol. 20, No. 3, pp. 333-357, 1998.

 [9]

T. M. CHAN, Output-sensitive results on convex hulls, extreme points, and related problems, Discrete Comput. Geom., Vol. 16, No. 4, pp. 369-387, 1996.

 [10]

D. R. CHAND AND S. S. KAPUR, An algorithm for convex polytopes, J. Assoc. Comput. Mach., Vol. 17, No. 78-86, 1970.

 [11]

R. CHANDRASEKARAN, S. N. KABADI, AND K. G. MURTY, Some NP-complete problems in linear programming, Oper. Res. Lett., Vol. 1, No. 3, pp. 101-104, 1982.

 [12]

B. CHAZELLE, An optimal convex hull algorithm in any fixed dimension, Discrete Comput. Geom., Vol. 10, No. 4, pp. 377-409, 1993.

 [13]

G. DANARAJ AND V. KLEE, A representation of 2-dimensional pseudomanifolds and its use in the design of a linear-time shelling algorithm., Ann. Discrete Math., Vol. 2, pp. 53-63, 1978.

 [14]

M. E. DYER, The complexity of vertex enumeration methods, Math. Oper. Res, Vol. 8, pp. 381-402, 1983.

 [15]

M. E. DYER AND A. M. FRIEZE, On the complexity of computing the volume of a polyhedron., SIAM J. Comput., Vol. 17, No. 5, pp. 967-974, 1988.

 [16]

M. E. DYER, A. M. FRIEZE, AND R. KANNAN, A random polynomial-time algorithm for approximating the volume of convex bodies., J. Assoc. Comput. Mach., Vol. 38, No. 1, pp. 1-17, 1991.

 [17]

B. C. EAVES AND R. M. FREUND, Optimal scaling of balls and polyhedra, Math. Program., Vol. 23, pp. 138-147, 1982.

 [18]

J. EDMONDS, Paths, trees, and flowers, Can. J. Math., Vol. 17, pp. 449-467, 1965.

 [19]

J. ERICKSON, New lower bounds for convex hull problems in odd dimensions, SIAM J. Comput., Vol. 28, No. 4, pp. 1198-1214, 1999.

 [20]

R. M. FREUND AND J. B. ORLIN, On the complexity of four polyhedral set containment problems, Math. Program., Vol. 33, pp. 139-145, 1985.

 [21]

A. M. FRIEZE AND S.-H. TENG, On the complexity of computing the diameter of a polytope, Comput. Complexity, Vol. 4, pp. 207-219, 1994.

 [22]

K. FUKUDA, T. M. LIEBLING, AND F. MARGOT, Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron, Comput. Geom., Vol. 8, pp. 1-12, 1997.

 [23]

M. R. GAREY AND D. S. JOHNSON, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San Francisco, 1979.

 [24]

B. GÄRTNER, The random facet simplex algorithm on combinatorial cubes. Manuscript, February 2001.

 [25]

E. GAWRILOW AND M. JOSWIG, Homepage of polymake. http://www.math.tu-berlin.de/diskregeom/polymake/.

 [26]

E. GAWRILOW AND M. JOSWIG, polymake: A framework for analyzing convex polytopes, in Polytopes -- Combinatorics and Computation, G. Kalai and G. M. Ziegler, eds., Birkhäuser, 2000, pp. 43-74.

 [27]

-------, polymake: an approach to modular software design in computational geometry, in Proc. 17th ACM Ann. Symp. Comput. Geom., pp. 222-231, 2001.

 [28]

P. GRITZMANN, V. KLEE, AND D. LARMAN, Largest j-simplices in n-polytopes, Discrete Comput. Geom., Vol. 13, pp. 477-515, 1995.

 [29]

J. E. HOPCROFT AND R. E. TARJAN, Dividing a graph into triconnected components, SIAM J. Comput., Vol. 2, pp. 135-158, 1973.

 [30]

-------, Efficient planarity testing, J. Assoc. Comput. Mach., Vol. 21, pp. 549-568, 1974.

 [31]

C. S. ILIOPOULOS, Worst-case complexity bounds on algorithms for computing the canonical structure of finite Abelian groups and the Hermite and Smith normal forms of an integer matrix, SIAM J. Comput., Vol. 18, No. 4, pp. 658-669, 1989.

 [32]

M. JOSWIG, V. KAIBEL, AND F. KÖRNER, On the k-systems of a simple polytope, Isr. J. Math., Vol. 129, pp. 109-118, 2002.

 [33]

V. KAIBEL AND M. E. PFETSCH, Computing the face lattice of a polytope from its vertex-facet incidences, Comput. Geom., Vol. 23, No. 3, pp. 281-290, 2002.

 [34]

V. KAIBEL AND A. SCHWARTZ, On the complexity of isomorphism problems related to polytopes, tech. report, TU Berlin, 2001. Submitted.

 [35]

G. KALAI, A simple way to tell a simple polytope from its graph, J. Comb. Theory, Ser. A, Vol. 49, No. 2, pp. 381-383, 1988.

 [36]

G. KALAI, A subexponential randomized simplex algorithm, in Proc. 24th Ann. ACM Symp. Theory Comput., Victoria, pp. 475-482, 1992, ACM Press.

 [37]

N. KARMARKAR, A new polynomial-time algorithm for linear programming, Combinatorica, Vol. 4, pp. 373-395, 1984.

 [38]

L. KHACHIYAN, A polynomial algorithm in linear programming, Sov. Math., Dokl., Vol. 20, pp. 191-194, 1979.

 [39]

P. KLEINSCHMIDT AND S. ONN, Signable posets and partitionable simplicial complexes., Discrete Comput. Geom., Vol. 15, No. 4, pp. 443-466, 1996.

 [40]

N. LINIAL, Hard enumeration problems in geometry and combinatorics, SIAM J. Alg. Disc. Math., Vol. 7, No. 2, pp. 331-335, 1986.

 [41]

E. M. LUKS, Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Comput. Syst. Sci., Vol. 25, pp. 42-65, 1982.

 [42]

J. MATOUSEK, M. SHARIR, AND E. WELZL, A subexponential bound for linear programming, Algorithmica, Vol. 16, No. 4-5, pp. 498-516, 1996.

 [43]

P. MCMULLEN, The maximum numbers of faces of a convex polytope, Mathematika, Vol. 17, pp. 179-184, 1970.

 [44]

N. MEGIDDO, Linear programming in linear time when the dimension is fixed, J. Assoc. Comput. Mach., Vol. 31, pp. 114-127, 1984.

 [45]

K. MEHLHORN AND P. MUTZEL, On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm, Algorithmica, Vol. 16, No. 2, pp. 233-242, 1996.

 [46]

H. MINKOWSKI, Geometrie der Zahlen (Geometry of numbers). Teubner Verlag, Leipzig, 1886 and 1910; reprinted by Chelsea, New York, 1953, and by Johnson, New York, 1968. (German).

 [47]

N. E. MNËV, The universality theorems on the classification problem of configuration varieties and convex polytopes varieties, in Topology and Geometry - Rohlin Seminar, O. Y. Viro, ed., No. 1346 in Lecture Notes in Mathematics, Springer-Verlag, 1988, pp. 527-543.

 [48]

J. R. MUNKRES, Elements of Algebraic Topology, Addison-Wesley, Menlo Park CA, 1984.

 [49]

K. G. MURTY, A fundamental problem in linear inequalities with applications to the travelling salesman problem, Math. Program., Vol. 2, pp. 296-308, 1972.

 [50]

S. D. NOBLE, Recognising a partitionable simplicial complex is in NP, Discrete Math., Vol. 152, pp. 303-305, 1996.

 [51]

A. PACKER, NP-hardness of largest contained and smallest containing simplices for V- and H-polytopes, Discrete Comput. Geom., Vol. 28, pp. 349-377, 2002.

 [52]

C. H. PAPADIMITRIOU AND M. YANNAKAKIS, On recognizing integer polyhedra, Combinatorica, Vol. 10, No. 1, pp. 107-109, 1990.

 [53]

M. E. PFETSCH, The Maximum Feasible Subsystem Problem and Vertex-Facet Incidences of Polyhedra, PhD thesis, TU Berlin, 2002.

 [54]

J. S. PROVAN, Efficient enumeration of the vertices of polyhedra associated with network LP's, Math. Program., Vol. 63, pp. 47-64, 1994.

 [55]

J. RICHTER-GEBERT, Realization Spaces of Polytopes, No. 1643 in Lecture Notes in Mathematics, Springer-Verlag, 1996.

 [56]

G.-C. ROTA, On the foundations of combinatorial theory - I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie, Vol. 2, pp. 340-368, 1964.

 [57]

A. SCHRIJVER, Theory of linear and integer programming, Wiley-Interscience, 1986.

 [58]

R. SEIDEL, Constructing higher-dimensional convex hulls at logarithmic cost per face, in Proc. 18th Ann. ACM Sympos. Theory Comput., pp. 404-413, 1986.

 [59]

-------, Convex hull computations, in Handbook of Discrete and Computational Geometry, J. Goodman and J. O'Rouke, eds., CRC Press, Boca Raton, 1997, ch. 19.

 [60]

R. P. STANLEY, Balanced Cohen-Macaulay complexes, Trans. Am. Math. Soc., Vol. 249, pp. 139-157, 1979.

 [61]

E. STEINITZ AND H. RADEMACHER, Vorlesungen über die Theorie der Polyeder, Springer Verlag, 1934. Reprint 1976.

 [62]

G. F. SWART, Finding the convex hull facet by facet, J. Algorithms, Vol. 6, pp. 17-48, 1985.

 [63]

T. SZABÓ AND E. WELZL, Unique sink orientations of cubes, tech. report, ETH Zürich, 2001. To appear in: Proc. 42nd Ann. Sympos. Found. Computer Science, Las Vegas, Oct 14-17, 2001.

 [64]

W. T. TUTTE, How to draw a graph, Proc. Lond. Math. Soc., III. Ser., Vol. 13, pp. 743-768, 1963.

 [65]

H. WEYL, Elementare Theorie der konvexen Polyeder, Comment. Math. Helv., Vol. 7, pp. 290-306, 1935.

 [66]

G. M. ZIEGLER, Lectures on Polytopes, Springer-Verlag, 1995. Revised edition 1998.