Extensions of dually bipartite regular polytopes

This paper addresses the problem of finding abstract regular polytopes with preassigned facets and preassigned last entry of the Schläfli symbol. Using C-group permutation representation (CPR) graphs we give a solution to this problem for dually bipartite regular polytopes when the last entry of the Schläfli symbol is even. This construction is related to a previous construction by Schulte that solves the problem when the entry of the Schläfli symbol is 6.     

Representing the sporadic Archimedean polyhedra as abstract polytopes

We present the results of an investigation into the representations of Archimedean polyhedra (those polyhedra containing only one type of vertex figure) as quotients of regular abstract polytopes. Two methods of generating these presentations are discussed, one of which may be applied in a general setting, and another which makes use of a regular polytope with the same automorphism group as the desired quotient. Representations of the 14 sporadic Archimedean polyhedra (including the pseudorhombicuboctahedron) as quotients of regular abstract polyhedra are obtained, and summarised in a table. The information is used to characterize which of these polyhedra have acoptic Petrie schemes (that is, have well-defined Petrie duals).     

Extensions of regular polytopes with preassigned Schläfli symbol

We say that a (d+1)-polytope P is an extension of a polytope K if the facets or the vertex figures of P are isomorphic to K. The Schläfli symbol of any regular extension of a regular polytope is determined except for its first or last entry. For any regular polytope K we construct regular extensions with any even number as first entry of the Schläfli symbol. These extensions are lattices if K is a lattice. Moreover, using the so-called CPR graphs we provide a more general way of constructing extensions of polytopes.     

On locally spherical polytopes of type {5, 3, 5}

There are only finitely many locally projective regular polytopes of type {5, 3, 5}. They are covered by a locally spherical polytope whose automorphism group is J₁×J₁×L₂(19), where J₁ is the first Janko group, of order 175560, and L₂(19) is the projective special linear group of order 3420. This polytope is minimal, in the sense that any other polytope that covers all locally projective polytopes of type {5, 3, 5} must in turn cover this one.     

On weakly convex star-shaped polyhedra

Weakly convex polyhedra which are star-shaped with respect to one of their vertices are infinitesimally rigid. This is a partial answer to the question as to whether every decomposable weakly convex polyhedron is infinitesimally rigid. The proof is based on a recent result of Izmestiev on the geometry of convex caps.     

A family of easy polyhedra

Let E be a finite set and a family of subsets of E such that the symmetric difference of any two members of this family is at least 2. Let be the complement of in , the set of the subsets of E. In this paper we characterize the convex hull of the characteristic vectors of the elements of . We consider also the polar of these polyhedra and study their links with some well known polyhedra. Note from the Editors  This paper was originally submitted directly to a guest editor appointed for a planned special issue dedicated to the memory of Claude Berge. Unfortunately the issue never materialized and had to be canceled. It was only recently discovered that this paper was never processed.     

Refold rigidity of convex polyhedra

We show that every convex polyhedron may be unfolded to one planar piece, and then refolded to a different convex polyhedron. If the unfolding is restricted to cut only edges of the polyhedron, we identify several polyhedra that are “edge-refold rigid” in the sense that each of their unfoldings may only fold back to the original. For example, each of the 43,380 edge unfoldings of a dodecahedron may only fold back to the dodecahedron, and we establish that 11 of the 13 Archimedean solids are also edge-refold rigid. We begin the exploration of which classes of polyhedra are and are not edge-refold rigid, demonstrating infinite rigid classes through perturbations, and identifying one infinite nonrigid class: tetrahedra.     

On box totally dual integral polyhedra

Edmonds and Giles introduced the class of box totally dual integral polyhedra as a generalization of submodular flow polyhedra. In this paper a geometric characterization of these polyhedra is given. This geometric result is used to show that each TDI defining system for a box TDI polyhedron is in fact a box TDI system, that the class of box TDI polyhedra is in co-NP and is closed under taking projections and dominants, that the class of box perfect graphs is in co-NP, and a result of Edmonds and Giles which is related to the facets of box TDI polyhdera.Supported by a grant from the Alexander von Humboldt-Stiftung.     

On polyhedra induced by point sets in space

Given a set S of n?3 points in the plane (not all on a line) it is well known that it is always possible to polygonize S, i.e., construct a simple polygon P such that the vertices of P are precisely the given points in S. For example, the shortest circuit through S is a simple polygon. In 1994, Grünbaum showed that an analogous theorem holds in R³. More precisely, if S is a set of n?4 points in R³ (not all of which are coplanar) then it is always possible to polyhedronize S, i.e., construct a simple (sphere-like) polyhedron P such that the vertices of P are precisely the given points in S. Grünbaum's constructive proof may yield Schönhardt polyhedra that cannot be triangulated. In this paper several alternative algorithms are proposed for constructing such polyhedra induced by a set of points, which may always be triangulated, and which enjoy several other useful properties as well. Such properties include polyhedra that are star-shaped, have Hamiltonian skeletons, and admit efficient point-location queries. We show that polyhedronizations with a variety of such useful properties can be computed efficiently in O(nlogn) time. Furthermore, we show that a tetrahedralized, xy-monotonic, polyhedronization of S may be computed in time O(n^1+ε), for any ε>0.     

Spatial bi-stacked central configurations formed by two dual regular polyhedra

In this paper we prove the existence of two new families of spatial stacked central configurations, one consisting of eight equal masses on the vertices of a cube and six equal masses on the vertices of a regular octahedron, and the other one consisting of twenty masses at the vertices of a regular dodecahedron and twelve masses at the vertices of a regular icosahedron. The masses on the two different polyhedra are in general different. We note that the cube and the octahedron, the dodecahedron and the icosahedron are dual regular polyhedra. The tetrahedron is itself dual. There are also spatial stacked central configurations formed by two tetrahedra, one and its dual.     

Reprint of: Refold rigidity of convex polyhedra

We show that every convex polyhedron may be unfolded to one planar piece, and then refolded to a different convex polyhedron. If the unfolding is restricted to cut only edges of the polyhedron, we identify several polyhedra that are “edge-refold rigid” in the sense that each of their unfoldings may only fold back to the original. For example, each of the 43,380 edge unfoldings of a dodecahedron may only fold back to the dodecahedron, and we establish that 11 of the 13 Archimedean solids are also edge-refold rigid. We begin the exploration of which classes of polyhedra are and are not edge-refold rigid, demonstrating infinite rigid classes through perturbations, and identifying one infinite nonrigid class: tetrahedra.     

Structures of polyhedra determined by submodular functions on crossing families

The present paper shows that for any submodular functionf on a crossing family with , if the polyhedron is nonempty, then there exist a unique distributive lattice with and a unique submodular function with such thatB(f) coincides with the base polyhedron associated with the submodular system . Here, iff is integer-valued, thenf ₁ is also integer-valued. Based on this fact, we also show the relationship between the independent-flow problem considered by the author and the minimum cost flow problem considered by J. Edmonds and R. Giles.     

On perfect graphs and polyhedra with (0, 1)-valued extreme points

LetC andA be (0, 1)-valued matrices with no zero columns. Fulkerson has shown that the extreme points of {x: Cx 1,x 0} are given by the rows ofA and their projections and the extreme points of {x: Ax 1,x 0} are given by the rows ofC and their projections if and only if the maximal rows ofC andA are the incidence vectors of maximal cliques and anticliques, respectively, of a perfect graph. This theorem is discussed and a new proof is given for the only if implication.Research partially supported by grant ENG 76-09936 from the National Science Foundation to Cornell University and by Sonderforschungsbereich 21 (DFG), Institut für Operations Research, Universität Bonn.     

Binary group and Chinese postman polyhedra

A new proof of the characterization of the Chinese postman polyhedra is given. In developing this proof, a theorem of Gomory about homomorphic lifting of facets for group polyhedra is generalized to subproblems. Some results for the Chinese postman problem are generalized to binary group problems. In addition, a connection is made between Fulkerson's blocking polyhedra and a blocking pair of binary group problems. A connection is also developed between minors and lifting of facets for group problems.     

Two-edge connected spanning subgraphs and polyhedra

This paper studies the problem of finding a two-edge connected spanning subgraph of minimum weight. This problem is closely related to the widely studied traveling salesman problem and has applications to the design of reliable communication and transportation networks. We discuss the polytope associated with the solutions to this problem. We show that when the graph is series-parallel, the polytope is completely described by the trivial constraints and the so-called cut constraints. We also give some classes of facet defining inequalities of this polytope when the graph is general.Research supported in part by the Natural Sciences and Engineering Research Council of Canada and CP Rail and the German Research Association (Deutsche Forschungsgemeinschaft SFR 303).     

Representing polyhedra: faces are better than vertices

This paper investigates the reconstruction of planar-faced polyhedra given their spherical dual representation. The spherical dual representation for any genus 0 polyhedron is shown to be unambiguous and to be uniquely reconstructible in polynomial time. It is also shown that when the degree of the spherical dual representation is at most four, the representation is unambiguous for polyhedra of any genus. The first result extends, in the case of planar-faced polyhedra, the well known result that a vertex or face connectivity graph represents a polyhedron unambiguously when the graph is triconnected and planar. The second result shows that when each face of a polyhedron of arbitrary genus has at most four edges, the polyhedron can be reconstructed uniquely. This extends the previous result that a polyhedron can be uniquely reconstructed when each face of the polyhedron is triangular. As a consequence of this result, faces are a more powerful representation than vertices for polyhedra whose faces have three or four edges. A result of the reconstruction algorithm is that high level features of the polyhedron are naturally extracted. Both results explicitly use the fact that the faces of the polyhedron are planar. It is conjectured that the spherical dual representation is unambiguous for polyhedra of any genus.