Cyclic Degrees of 3-Polytopes

 A precise upper bound is obtained for the minimum cyclic vertex degree in a 3-polytope with specified maximum face size. This implies improvements to some known upper bounds for the cyclic chromatic numbers of 3-polytopes. Received: August 18, 1997 Revised: August 24, 1998     

Heights of Minor Faces in 3-Polytopes

Siberian Mathematical Journal - Each 3-polytope has obviously a face  $ f $ of degree $ d(f) $ at most 5 which is called minor. The height $ h(f) $ of $ f $ is...     

A Structural Property of Convex 3-Polytopes

In this paper we prove that each convex 3-polytope contains a path on three vertices with restricted degrees which is one of the ten types. This result strengthens a theorem by Kotzig that each convex 3-polytope has an edge with the degree sum of its end vertices at most 13.     

Minimal Simplicial Dissections and Triangulations of Convex 3-Polytopes

This paper addresses three questions related to minimal triangulations of a three-dimensional convex polytope P . • Can the minimal number of tetrahedra in a triangulation be decreased if one allows the use of interior points of P as vertices? • Can a dissection of P use fewer tetrahedra than a triangulation? • Does the size of a minimal triangulation depend on the geometric realization of P ? The main result of this paper is that all these questions have an affirmative answer. Even stronger, the gaps of size produced by allowing interior vertices or by using dissections may be linear in the number of points. Received August 16, 1999, and in revised form February 29, 2000. Online publication May 19, 2000.     

Low Faces of Restricted Degree in 3-Polytopes

Siberian Mathematical Journal - The degree of a vertex or face in a 3-polytope is the number of incident edges. A k-face is one of degree k, a k−-face has degree at most k. The height of a...     

Shelling Polyhedral 3-Balls and 4-Polytopes

There is a long history of constructions of nonshellable triangulations of three-dimensional (topological) balls. This paper gives a survey of these constructions, including Furch's 1924 construction using knotted curves, which also appears in Bing's 1962 survey of combinatorial approaches to the Poincaré conjecture, Newman's 1926 explicit example, and M. E. Rudin's 1958 nonshellable triangulation of a tetrahedron with only 14 vertices (all on the boundary) and 41 facets. Here an (extremely simple) new example is presented: a nonshellable simplicial three-dimensional ball with only 10 vertices and 21 facets. It is further shown that shellings of simplicial 3 -balls and 4 -polytopes can ``get stuck': simplicial 4 -polytopes are not in general ``extendably shellable.' Our constructions imply that a Delaunay triangulation algorithm of Beichl and Sullivan, which proceeds along a shelling of a Delaunay triangulation, can get stuck in the three-dimensional version: for example, this may happen if the shelling follows a knotted curve. Received November 21, 1995, and in revised form September 20, 1996.     

Approximation for Minimum Triangulations of Simplicial Convex 3-Polytopes

A minimum triangulation of a convex 3-polytope is a triangulation that contains the minimum number of tetrahedra over all its possible triangulations. Since finding minimum triangulations of convex 3-polytopes was recently shown to be NP-hard, it becomes significant to find algorithms that give good approximation. In this paper we give a new triangulation algorithm with an improved approximation ratio 2 - Ω(1/\sqrt n ) , where n is the number of vertices of the polytope. We further show that this is the best possible for algorithms that only consider the combinatorial structure of the polytopes. Received August 5, 2000, and in revised form March 29, 2001, and May 3, 2001. Online publication October 12, 2001.     

Grid Orientations, (d,d + 2)-Polytopes, and Arrangements of Pseudolines

We investigate the combinatorial structure of linear programs on simple d-polytopes with d + 2 facets. These can be encoded by admissible grid orientations. Admissible grid orientations are also obtained through orientation properties of a planar point configuration or by the dual line arrangement. The point configuration and the polytope corresponding to the same grid are related through an extended Gale transform. The class of admissible grid orientations is shown to contain nonrealizable examples, i.e., there are admissible grid orientations which cannot be obtained from a polytope or a point configuration. It is shown, however, that every admissible grid orientation is induced by an arrangement of pseudolines. This later result is used to prove several nontrivial facts about admissible grid orientations.     

3-Colorable Even Embeddings on Closed Surfaces

It is known that for any closed surface F², every even embedding on F² with sufficiently large representativity is 4-colorable. In this paper, we shall characterize 3-colorable even embeddings on F² with sufficiently large representativity.     

Linkless and Flat Embeddings in 3-Space

We consider piecewise linear embeddings of graphs in 3-space ℝ³. Such an embedding is linkless if every pair of disjoint cycles forms a trivial link (in the sense of knot theory). Robertson, Seymour and Thomas (J. Comb. Theory, Ser. B 64:185–227, 1995) showed that a graph has a linkless embedding in ℝ³ if and only if it does not contain as a minor any of seven graphs in Petersen’s family (graphs obtained from K ₆ by a series of YΔ and ΔY operations). They also showed that a graph is linklessly embeddable in ℝ³ if and only if it admits a flat embedding into ℝ³, i.e. an embedding such that for every cycle C of G there exists a closed 2-disk D⊆ℝ³ with D∩G=∂D=C. Clearly, every flat embedding is linkless, but the converse is not true. We consider the following algorithmic problem associated with embeddings in ℝ³:     

Convex Drawings of Planar Graphs and the Order Dimension of 3-Polytopes

We define an analogue of Schnyder's tree decompositions for 3-connected planar graphs. Based on this structure we obtain: Let G be a 3-connected planar graph with f faces, then G has a convex drawing with its vertices embedded on the (f–1)×(f–1) grid. Let G be a 3-connected planar graph. The dimension of the incidence order of vertices, edges and bounded faces of G is at most 3.The second result is originally due to Brightwell and Trotter. Here we give a substantially simpler proof.     

Embeddings in the 3/4 range

We give a complete obstruction to turning an immersion f:M^m→Rⁿ into an embedding when 3n?4m+5. It is a secondary obstruction, and exists only when the primary obstruction, due to André Haefliger, vanishes. The obstruction lives in a twisted cobordism group, and its vanishing implies the existence of an embedding in the regular homotopy class of f in the range indicated. We use Tom Goodwillie's calculus of functors, following Michael Weiss, to help organize and prove the result.     

Convex Embeddings and Bisections of 3-Connected Graphs1

Given two disjoint subsets T ₁ and T ₂ of nodes in an undirected 3-connected graph G = (V, E) with node set V and arc set E, where and are even numbers, we show that V can be partitioned into two sets V ₁ and V ₂ such that the graphs induced by V ₁ and V ₂ are both connected and holds for each j = 1,2. Such a partition can be found in time. Our proof relies on geometric arguments. We define a new type of convex embedding of k-connected graphs into real space R ^k-1 and prove that for k = 3 such an embedding always exists. ¹ A preliminary version of this paper with title Bisecting Two Subsets in 3-Connected Graphs appeared in the Proceedings of the 10th Annual International Symposium on Algorithms and Computation, ISAAC 99, (A. Aggarwal, C. P. Rangan, eds.), Springer LNCS 1741, 425–434, 1999.     

Describing Neighborhoods of 5-Vertices in a Class of 3-Polytopes with Minimum Degree 5

Lebesgue proved in 1940 that each 3-polytope with minimum degree 5 contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences(6, 6, 7, 7, 7), (6, 6, 6, 7, 9), (6, 6, 6, 6, 11)(5, 6, 7, 7, 8), (5, 6, 6, 7, 12), (5, 6, 6, 8, 10), (5, 6, 6, 6, 17)(5, 5, 7, 7, 13), (5, 5, 7, 8, 10), (5, 5, 6, 7, 27), (5, 5, 6, 6,∞), (5, 5, 6, 8, 15), (5, 5, 6, 9, 11)(5, 5, 5, 7, 41), (5, 5, 5, 8, 23), (5, 5, 5, 9, 17), (5, 5, 5, 10, 14), (5, 5, 5, 11, 13).We prove that each 3-polytope with minimum degree 5 without vertices of degree from 7 to 10 contains a 5-vertex whose set of degrees of its neighbors is majorized by one of the following sequences: (5, 6, 6, 5, ∞), (5, 6, 6, 6, 15), and (6, 6, 6, 6, 6), where all parameters are tight.     

Embeddings of curves

In this paper a numerical criterion for divisors on a smooth projective surface to be very ample is given. The idea is to restrict a given divisor to a sufficient number of (not necessarily, irreducible nor reduced) curfes on the surface and prove the very ampleness of the restriction. At the end we given an application to Bordiga surfaces.     

Cubical 4-Polytopes with Few Vertices

A cubical polytope is a convex polytope all of whose facets are conbinatorial cubes. A d-polytope Pis called almost simple if, in the graph of P, each vertex of Pis d-valent of (d+ 1)-valent. It is known that, for d> 4, all but one cubical d-polytopes with up to 2^d+1vertices are almost simple, which provides a complete enumeration of all the cubical d-polytopes with up to 2^d+1vertices. We show that this result is also true for d=4.