A German translation of Euler's articles on the polyhedron formula now available on the World Wide Web

The two articles on the polyhedron formula Euler published in his lifetime, Eneström 230 and 231, are now available on the World Wide Web in German translation.     

Optimum matching forests II: General weights

Matching forests generalize branchings in a directed graph and matchings in an undirected graph. We present an efficient algorithm, the PMF Algorithm, for the problem: given a mixed graphG and a real weight on each of its edges, find a perfect matching forest of maximum weight-sum. The PMF Algorithm proves the sufficiency of a linear system which definesP ⁼ (G) andP(G), the convex hull of incidence vectors of perfect matching forests and matching forests respectively ofG. The algorithm also provides a generalization of Tutte's theorem on the existence of perfect matchings in an undirected graph.Research partially supported by a N.R.C. of Canada Postdoctorate Fellowship.     

Hamiltonian properties of polyhedra with few 3-cuts—A survey

We give an overview of the most important techniques and results concerning the hamiltonian properties of planar 3-connected graphs with few 3-vertex-cuts. In this context, we also discuss planar triangulations and their decomposition trees. We observe an astonishing similarity between the hamiltonian behavior of planar triangulations and planar 3-connected graphs. In addition to surveying, (i) we give a unified approach to constructing non-traceable, non-hamiltonian, and non-hamiltonian-connected triangulations, and show that planar 3-connected graphs (ii) with at most one 3-vertex-cut are hamiltonian-connected, and (iii) with at most two 3-vertex-cuts are 1-hamiltonian, filling two gaps in the literature. Finally, we discuss open problems and conjectures.     

Enumerating pseudo-triangulations in the plane

In this paper, we study the problem of whether a polyhedron can be obtained from a net by folding along the creases. We show that this problem can be solved in polynomial time if the dihedral angle at each crease is given, and it becomes NP-hard if these angles are unknown. We also study the case when the net has rigid faces that should not intersect during the folding process.     

Distribution, structures and nonlinear properties of noncentrosymmetric niobates and tantalates

The distribution of 117 noncentrosymmetric niobates and tantalates over different crystal systems and types of space formation of Nb, Ta-O polyhedrons have been revealed. The dependence of polyhedron space formation in the crystal lattice of the compound on stoichiometric concentration (SC) of niobium and tantalum is established. Individual Nb, Ta-O octahedrons are found for SC=19-7.5, and chains and layers of the octahedrons appear in the range SC=11.0-5.2. Only frame formations of Nb, Ta-O octahedrons are possible under SC<5.2.     

Extended formulations for the A-cut problem

LetG=(V, E) be an undirected graph andA⊆V. We consider the problem of finding a minimum cost set of edges whose deletion separates every pair of nodes inA. We consider two extended formulations using both node and edge variables. An edge variable formulation has previously been considered for this problem (Chopra and Rao (1991), Cunningham (1991)). We show that the LP-relaxations of the extended formulations are stronger than the LP-relaxation of the edge variable formulation (even with an extra class of valid inequalities added). This is interesting because, while the LP-relaxations of the extended formulations can be solved in polynomial time, the LP-relaxation of the edge variable formulation cannot. We also give a class of valid inequalities for one of the extended formulations. Computational results using the extended formulations are performed.     

Packing circuits in matroids

The purpose of this paper is to characterize all matroids M that satisfy the following minimax relation: for any nonnegative integral weight function w defined on E(M),