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.     

Cutting a Convex Polyhedron Out of a Sphere

Given a convex polyhedron P of n vertices inside a sphere Q, we give an O(n ³)-time algorithm that cuts P out of Q by using guillotine cuts and has cutting cost O(log² n) times the optimal.     

Hamiltonicity in (0–1)-polyhedra

The graph G(P) of a polyhedron P has a node corresponding to each vertex of P and two nodes are adjacent in G(P) if and only if the corresponding vertices of P are adjacent on P. We show that if P ? $\text{R}$ⁿ is a polyhedron, all of whose vertices have (0–1)-valued coordinates, then (i) if G(P) is bipartite, the G(P) is a hypercube; (ii) if G(P) is nonbipartite, then G(P) is hamilton connected. It is shown that if P ? $\text{R}$ⁿ has (0–1)-valued vertices and is of dimension d (≤n) then there exists a polyhedron P′ ? $\text{R}$^d having (0–1)-valued vertices such that $\text{G(P) ? G(P′)}$. Some combinatorial consequences of these results are also discussed.     

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.     

Characterization of the types of maximum noninteger vertices in the relaxation polyhedron of the four-index axial assignment problem

For the relaxation polyhedron M(4, n) in the four-index axial assignment problem of order n, n ≥ 3, a characterization of all possible types (except for a single case) of maximum noninteger vertices, i.e., vertices with 4n — 3 fractional components is proposed. A formula enumerating all the maximum noninteger vertices of the same type in M(4, n) is derived.     

On infinite graphs with a specified number of colorings

In this paper we construct a planar graph of degree four which admits exactly N_u 3-colorings, we prove that such a graph must have degree at least four, and we consider various generalizations. We first allow our graph to have either one or two vertices of infinite degree and/or to admit only finitely many colorings and we note how this effects the degrees of the remaining vertices. We next consider n-colorings for n>3, and we construct graphs which we conjecture (but cannot prove) are of minimal degree. Finally, we consider nondenumerable graphs, and for every 3 <n<ω and every infinite cardinal k we construct a graph of cardinality k which admits exactly kn-colorings. We also show that the number of n-colorings of a denumerable graph can never be strictly between N_u and 2^N_u and that an appropriate generalization holds for at least certain nondenumerable graphs.     

Hamiltonicity and combinatorial polyhedra

We say that a polyhedron with 0–1 valued vertices is combinatorial if the midpoint of the line joining any pair of nonadjacent vertices is the midpoint of the line joining another pair of vertices. We show that the class of combinatorial polyhedra includes such well-known classes of polyhedra as matching polyhedra, matroid basis polyhedra, node packing or stable set polyhedra and permutation polyhedra. We show the graph of a combinatorial polyhedron is always either a hypercube (i.e., isomorphic to the convex hull of a k-dimension unit cube) or else is hamilton connected (every pair of nodes is the set of terminal nodes of a hamilton path). This implies several earlier results concerning special cases of combinatorial polyhedra.     

The extremal graph problem of the icosahedron

P. Turán has asked the following question:Let I¹² be the graph determined by the vertices and edges of an icosahedron. What is the maximum number of edges of a graph Gⁿ of n vertices if Gⁿ does not contain I¹² as a subgraph?We shall answer this question by proving that if n is sufficiently large, then there exists only one graph having maximum number of edges among the graphs of n vertices and not containing I¹². This graph Hⁿ can be defined in the following way:Let us divide n ? 2 vertices into 3 classes each of which contains [$\text{(n?2)}\text{3}$] or $\text{[}\text{(n?2)}\text{3}\text{] + 1}$ vertices. Join two vertices iff they are in different classes. Join two vertices outside of these classes to each other and to every vertex of these three classes.     

Metrics and undirected cuts

Suppose thatG is an undirected graph whose edges have nonnegative integer-valued lengthsl(e), and that {s ₁,t ₁},?, {s _m ,t _m } are pairs of its vertices. Can one assign nonnegative weights to the cuts ofG such that, for each edgee, the total weight of cuts containinge does not exceedl(e) and, for eachi, the total weight of cuts ‘separating’s _i andt _i is equal to the distance (with respect tol) betweens _i andt _i ? Using linear programming duality, it follows from Papernov's multicommodity flow theorem that the answer is affirmative if the graph induced by the pairs {s ₁,t ₁},?, {s _m ,t _m } is one of the following: (i) the complete graph with four vertices, (ii) the circuit with five vertices, (iii) a union of two stars. We prove that if, in addition, each circuit inG has an even length (with respect tol) then there exists a suitable weighting of the cuts with the weights integer-valued; moreover, an algorithm of complexity O(n ³) (n is the number of vertices ofG) is developed for solving such a problem. Also a class of metrics decomposable into a nonnegative linear combination of cut-metrics is described, and it is shown that the separation problem for cut cones isNP-hard.     

A bound on the total size of a cut cover

A cycle cover (cut cover) of a graph G is a collection of cycles (cuts) of G that covers every edge of G at least once. The total size of a cycle cover (cut cover) is the sum of the number of edges of the cycles (cuts) in the cover.We discuss several results for cycle covers and the corresponding results for cut covers. Our main result is that every connected graph on n vertices and e edges has a cut cover of total size at most 2e-n+1 with equality precisely when every block of the graph is an odd cycle or a complete graph (other than K₄ or K₈). This corresponds to the result of Fan [J. Combin. Theory Ser. B 74 (1998) 353-367] that every graph without cut-edges has a cycle cover of total size at most e+n-1.     

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.     

Area-efficient planar straight-line drawings of outerplanar graphs

It is important to minimize the area of a drawing of a graph, so that the drawing can fit in a small drawing-space. It is well-known that a planar graph with n vertices admits a planar straight-line grid drawing with O(n²) area [H. de Fraysseix, J. Pach, R. Pollack, How to draw a planar graph on a grid, Combinatorica 10(1) (1990) 41-51; W. Schnyder, Embedding planar graphs on the grid, in: Proceedings of the First ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 138-148]. Unfortunately, there is a matching lower-bound of Ω(n²) on the area-requirements of the planar straight-line grid drawings of certain planar graphs. Hence, it is important to investigate important categories of planar graphs to determine if they admit planar straight-line grid drawings with o(n²) area.In this paper, we investigate an important category of planar graphs, namely, outerplanar graphs. We show that an outerplanar graph G with degree d admits a planar straight-line grid drawing with area O(dn^1.48) in O(n) time. This implies that if d=o(n^0.52), then G can be drawn in this manner in o(n²) area.     

On edges crossing few other edges in simple topological complete graphs

We study the existence of edges having few crossings with the other edges in drawings of the complete graph (more precisely, in simple topological complete graphs). A topological graphT=(V,E) is a graph drawn in the plane with vertices represented by distinct points and edges represented by Jordan curves connecting the corresponding pairs of points (vertices), passing through no other vertices, and having the property that any intersection point of two edges is either a common end-point or a point where the two edges properly cross. A topological graph is simple if any two edges meet in at most one common point.Let h=h(n) be the smallest integer such that every simple topological complete graph on n vertices contains an edge crossing at most h other edges. We show that Ω(n^3/2)≤h(n)≤O(n²/log^1/4n). We also show that the analogous function on other surfaces (torus, Klein bottle) grows as cn².     

Orthogonal Laurent polynomials and the strong Hamburger moment problem

This paper is concerned with the strong Hamburger moment problem (SHMP): For a given double sequence of real numbers C = {c_n}^∞_?∞, does there exist a real-valued, bounded, non-decreasing function ψ on (?∞, ∞) with infinitely many points of increase such that for every integer n, c_n = ∝^∞_?∞ (?t)ⁿdψ(t)? Necessary and sufficient conditions for the existence of such a function ψ are given in terms of the positivity of certain Hankel determinants associated with C. Our approach is made through the study of orthogonal (and quasi-orthogonal) Laurent polynomials (referred to here as L-polynomials) and closely related Gaussian-type quadrature formulas. In the proof of sufficiency an inner product for L-polynomials is defined in terms of the given double sequence C. Since orthogonal L-polynomials are believed to be of interest in themselves, some examples of specific systems are considered.     

Embedding Theorems for General Multianisotropic Spaces

An integral representation and embedding theorems for functions in multianisotropic Sobolev spaces are proved. Unlike in previous works, the general case where the characteristic Newton polyhedron in ?ⁿ has an arbitrary number of vertices is considered.     

On Levels in Arrangements of Surfaces in Three Dimensions

A favorite open problem in combinatorial geometry is to determine the worst-case complexity of a level in an arrangement. Up to now, nontrivial upper bounds in three dimensions are known only for the linear cases of planes and triangles. We propose the first technique that can deal with more general surfaces in three dimensions. For example, in an arrangement of n ??pseudo-planes?? or ??pseudo-spherical patches?? (where the main criterion is that each triple of surfaces has at most two common intersections), we prove that there are at most O(n ^2.997) vertices at any given level.     

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.     

Cyclic group blocking polyhedra

Gomory (Linear Algebra Appl 2:451–558, 1969) gave a subadditive characterization of the facets of the group polyhedron. Although there are exponentially many facets (see Gomory and Johnson in Math Program 3:359–389, 1972, Example 4.6) and exponentially many vertices for the group polyhedron for the master cyclic group problem, Gomory’s characterization of the non-trivial facets has polynomially many subadditive inequalities, in fact of order |G|² for a finite Abelian group G. We reduce this subadditive inequality system to its minimal representation by a triple system of the same order and show the dimensionality of the polytope of non-trivial facets. The system of all triples corresponds to all solution vectors of length three into which every solution vector can be decomposed. Our minimal representation leads to a characterization of the vertices of length three. Gomory et al. (Math Program 96:321–339, 2003) introduced a shooting experiment involving solving the shooting linear program repeatedly to find important facets. We develop a topological network flow model of the dual problem of the shooting linear program in a reverse procedure from the decomposition of solution vectors into triples. Hunsaker (2003) gave a knapsack shooting experiment, which we use to find a simple pattern for the most hit knapsack facets.