On weakly neighborly polyhedral maps of arbitrary genus

A weakly neighborly polyhedral map (w.n.p. map) is a 2-dimensional cell-complex which decomposes a closed 2-manifold without boundary, such that for every two vertices there is a 2-cell containing them. We lay the foundation for an investigation of the w.n.p. maps of arbitrary genus. In particular we find all the w.n.p. maps of genus 0, we prove that for everyg> the number of w.n.p. maps of genusg (orientable or not) is finite, and we find an upper bound for the number of vertices in a w.n.p. map of genusg>0. This upper bound grows as (4g(^2/3) wheng→∞.     

A minimal design of order 11 on the 3-sphere

We prove that the 120 vertices of the regular four-dimensional polyhedron with the Schläfli symbol {3, 3, 5} form a minimal spheric design of order 11 onS ³. It is shown that the system of equal charges at these vertices provides the minimal potential energy among all systems of 120 equal charges onS ³.     

Edge-Directions of Standard Polyhedra with Applications to Network Flows

Recent results show that edge-directions of polyhedra play an important role in (combinatorial) optimization; in particular, a d-dimensional polyhedron with |D| distinct edge-directions has at most O(|D|^d-1) vertices. Here, we obtain a characterization of the directions of edges that are adjacent to a given vertex of a standard polyhedron of the form P = {x : Ax = b, l⩽ x⩽ u, tightening a standard necessary condition which asserts that such directions must be minimal support solutions of the homogenous equation Ax = 0 which are feasible at the given vertex. We specialize the characterization for polyhedra that correspond to network flows, obtaining a graph characterization of circuits which correspond to edge-directions. Applications to partitioning polyhedra are discussed. Research of these authors was supported by a grant from ISF – the Israel Science Foundation, by a VPR grant at the Technion, and by the Fund for the Promotion of Research at the Technion.     

Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm

We show that every orthogonal polyhedron homeomorphic to a sphere can be unfolded without overlap while using only polynomially many (orthogonal) cuts. By contrast, the best previous such result used exponentially many cuts. More precisely, given an orthogonal polyhedron with n vertices, the algorithm cuts the polyhedron only where it is met by the grid of coordinate planes passing through the vertices, together with Θ(n ²) additional coordinate planes between every two such grid planes.     

The maximum number of edges in a minimal graph of diameter 2

A graph g of diameter 2 is minimal if the deletion of any edge increases its diameter. Here the following conjecture of Murty and Simon is proved for n < n_o. If g has n vertices then it has at most n²/4 edges. The only extremum is the complete bipartite graph.     

Grid Vertex-Unfolding Orthogonal Polyhedra

An edge-unfolding of a polyhedron is produced by cutting along edges and flattening the faces to a net, a connected planar piece with no overlaps. A grid unfolding allows additional cuts along grid edges induced by coordinate planes passing through every vertex. A vertex-unfolding allows faces in the net to be connected at single vertices, not necessarily along edges. We show that any orthogonal polyhedra of genus zero has a grid vertex-unfolding. (There are orthogonal polyhedra that cannot be vertex-unfolded, so some type of “gridding” of the faces is necessary.) For any orthogonal polyhedron P with n vertices, we describe an algorithm that vertex-unfolds P in O(n ²) time. Enroute to explaining this algorithm, we present a simpler vertex-unfolding algorithm that requires a 3×1×1 refinement of the vertex grid. This is a significant revision of the preliminary version that appeared in [2]. J. O’Rourke’s research was supported by NSF award DUE-0123154.     

A four-vertex theorem for polygons and its generalization to polytopes

A vertex v of a convex polygon P is called minimal (respectively maximal) if the circle going through v and its neighbouring vertices encloses the interior of P (respectively has no vertex of P in its interior) The main result of this paper is a generalization to the convex polytopes of R ^d of the following theorem: Every convex polygon has at least two minimal and two maximal vertices The proof uses a duality theory which translates some spherical properties of a convex polytope of R ^d into combinatorial properties of a convex polyhedron of R ^d+1.     

Minimal ordered triangulations of surfaces

A finite simplicial complex is orderable if its simplices are the chains of a poset. For each closed surface an orderable triangulation is given that is minimal with respect to the number of vertices. The construction of minimal ordered triangulations implies that for each surface S the minimal number of vertices of a bipartite graph, which has a quadrilateral embedding into S, is equal to b(S) = ?4 + (16 – 8χ)^1/2?, where χ is the Euler characteristic of S.     

A polyhedron with alls—t cuts as vertices,and adjacency of cuts

Consider the polyhedron represented by the dual of the LP formulation of the maximums–t flow problem. It is well known that the vertices of this polyhedron are integral, and can be viewed ass–t cuts in the given graph. In this paper we show that not alls–t cuts appear as vertices, and we give a characterization. We also characterize pairs of cuts that form edges of this polyhedron. Finally, we show a set of inequalities such that the corresponding polyhedron has as its vertices alls–t cuts.Work done at the Department of Computer Science and Engineering, Indian Institute of Technology, Delhi, India.     

Note on irreducible triangulations of surfaces

In this paper, we shall show that an irreducible triangulation of a closed surface F² has at most cg vertices, where g stands for a genus of F² and c a constant. © 1995, John Wiley & Sons, Inc.     

Schnyder Woods for Higher Genus Triangulated Surfaces,with Applications to Encoding

Schnyder woods are a well-known combinatorial structure for plane triangulations, which yields a decomposition into three spanning trees. We extend here definitions and algorithms for Schnyder woods to closed orientable surfaces of arbitrary genus. In particular, we describe a method to traverse a triangulation of genus g and compute a so-called g-Schnyder wood on the way. As an application, we give a procedure to encode a triangulation of genus g and n vertices in 4n+O(glog (n)) bits. This matches the worst-case encoding rate of Edgebreaker in positive genus. All the algorithms presented here have execution time O((n+g)g) and hence are linear when the genus is fixed. Extended version of the article appeared in the Proc. of the ACM SoCG 2008. Part of the first author’s work was done during his visit to the CS Department of Université Libre de Bruxelles (Belgium).     

Geometric realizations for Dyck's regular map on a surface of genus 3

Klein's and Dyck's regular maps on Riemann surfaces of genus 3 were one impetus for the theory of regular maps, automorphic functions, and algebraic curves. Recently a polyhedral realization inE ³ of Klein's map was discovered [18], thereby underlining the strong analogy to the icosahedron. In this paper we show that Dyck's map can be realized inE ³ as a polyhedron of Kepler-Poinsot-type, i.e., with maximal symmetry and minimal self-intersections. Furthermore some closely related polyhedra and a Kepler-Poinsot-type realization of Sherk's regular map of genus 5 are discussed.     

Surfaces with pg = 2, K2 = 3 and a pencil of curves of genus 2

We classify minimal smooth surfaces of general type with K ² = 3, p _g = 2 which admit a fibration of curves of genus 2.We prove that they form an irreducible set of dimension 22 in their moduli space.      

On the difficulty of triangulating three-dimensional Nonconvex Polyhedra

A number of different polyhedraldecomposition problems have previously been studied, most notably the problem of triangulating a simple polygon. We are concerned with thepolyhedron triangulation problem: decomposing a three-dimensional polyhedron into a set of nonoverlapping tetrahedra whose vertices must be vertices of the polyhedron. It has previously been shown that some polyhedra cannot be triangulated in this fashion. We show that the problem of deciding whether a given polyhedron can be triangulated is NP-complete, and hence likely to be computationally intractable. The problem remains NP-complete when restricted to the case of star-shaped polyhedra. Various versions of the question of how many Steiner points are needed to triangulate a polyhedron also turn out to be NP-hard.This work was supported by National Science Foundation Grant CCR-8809040.     

Remarks on Normal Generation of Special Line Bundles on Algebraic Curves

Let L be a very ample line bundle with h ¹(L) ≥2 on a curve of genus g. We prove that L is normally generated if deg(L) ≥2g ? 1 ? 4h ¹(L) for large enough genus g.     

Decompositions and boundary coverings of non-convex fat polyhedra

We show that any locally-fat (or (α,β)-covered) polyhedron with convex fat faces can be decomposed into O(n) tetrahedra, where n is the number of vertices of the polyhedron. We also show that the restriction that the faces are fat is necessary: there are locally-fat polyhedra with non-fat faces that require Ω(n²) pieces in any convex decomposition. Furthermore, we show that if we want the tetrahedra in the decomposition to be fat themselves, then their number cannot be bounded as a function of n in the worst case. Finally, we obtain several results on the problem where we want to only cover the boundary of the polyhedron, and not its entire interior.     

On rainbowness of semiregular polyhedra

We introduce the rainbowness of a polyhedron as the minimum number k such that any colouring of vertices of the polyhedron using at least k colours involves a face all vertices of which have different colours. We determine the rainbowness of Platonic solids, prisms, antiprisms and ten Archimedean solids. For the remaining three Archimedean solids this parameter is estimated. Dedicated to Professor Miroslav Fiedler on the occasion of his 80th birthday.     

The Representation Polyhedron of a Semiorder

Let a finite semiorder, or unit interval order, be given. When suitably defined, its numerical representations are the solutions of a system of linear inequalities. They thus form a convex polyhedron. We show that the facets of the representation polyhedron correspond to the noses and hollows of the semiorder. Our main result is to prove that the system defining the polyhedron is totally dual integral. As a consequence, the coordinates of the vertices and the components of the extreme rays of the polyhedron are all integral multiples of a common value. Total dual integrality is in turn derived from a particular property of the oriented cycles in the directed graph of noses and hollows of a strictly upper diagonal step tableau. Our approach delivers also a new proof for the existence of the minimal representation of a semiorder, a concept originally discovered by Pirlot (Theory Decis 28:109–141, 1990). Finding combinatorial interpretations of the vertices and extreme rays of the representation polyhedron is left for future work.     

The negative cycles polyhedron and hardness of checking some polyhedral properties

Given a graph G=(V,E) and a weight function on the edges w:E→ℝ, we consider the polyhedron P(G,w) of negative-weight flows on G, and get a complete characterization of the vertices and extreme directions of P(G,w). Based on this characterization, and using a construction developed in Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008), we show that, unless P=NP, there is no output polynomial-time algorithm to generate all the vertices of a 0/1-polyhedron. This strengthens the NP-hardness result of Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes (Bussiech and Lübbecke in Comput. Geom., Theory Appl. 11(2):103–109, 1998). As further applications, we show that it is NP-hard to check if a given integral polyhedron is 0/1, or if a given polyhedron is half-integral. Finally, we also show that it is NP-hard to approximate the maximum support of a vertex of a polyhedron in ℝ ⁿ within a factor of 12/n.     

Minors in graphs of large girth

We show that for every odd integer g ≥ 5 there exists a constant c such that every graph of minimum degree r and girth at least g contains a minor of minimum degree at least cr^(g+1)/4. This is best possible up to the value of the constant c for g = 5, 7, and 11. More generally, a well‐known conjecture about the minimal order of graphs of given minimum degree and large girth would imply that our result gives the correct order of magnitude for all odd values of g. The case g = 5 of our result implies Hadwiger's conjecture for C₄‐free graphs of sufficiently large chromatic number. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 213–225, 2003