Upward Three-Dimensional Grid Drawings of Graphs

A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line segments representing the edges do not cross. Our aim is to produce three-dimensional grid drawings with small bounding box volume. Our first main result is that every -vertex graph with bounded degeneracy has a three-dimensional grid drawing with volume. This is the largest known class of graphs that have such drawings. A three-dimensional grid drawing of a directed acyclic graph (dag) is upward if every arc points up in the -direction. We prove that every dag has an upward three-dimensional grid drawing with volume, which is tight for the complete dag. The previous best upper bound was . Our main result concerning upward drawings is that every -colourable dag ( constant) has an upward three-dimensional grid drawing with volume. This result matches the bound in the undirected case, and improves the best known bound from for many classes of dags, including planar, series parallel, and outerplanar. Improved bounds are also obtained for tree dags. We prove a strong relationship between upward three-dimensional grid drawings, upward track layouts, and upward queue layouts. Finally, we study upward three-dimensional grid drawings with bends in the edges.Research of Vida Dujmovi is supported by NSERC. Research of David Wood is supported by the Government of Spain grant MEC SB2003-0270 and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

旋转双球和多球的Stokes流动

本文首先导出一类新旋转子的表达式.利用该旋转子的迭加,得到了双球和多球同轴旋转时所受的阻力矩,并证明了阻力矩是各球旋转角速度线性函数的结论.     

The Paneitz Curvature Problem on Lower-Dimensional Spheres

In this paper we prescribe a fourth order conformal invariant (the Paneitz curvature) on the n-spheres, with n∊{5,6}. Using dynamical and topological methods involving the study of critical points at infinity of the associated variational problem, we prove some existence results. Mathematics Subject Classifications (2000): 35J60, 53C21, 58J05, 35J30.     

The Generalized Axiom of Spheres

Some generalization is proposed for the axiom of spheres. A collection of Riemannian spaces is constructed which satisfy the generalized axiom of spheres, but do not satisfy the earlier-known axioms of submanifolds. The structure is found of the curvature tensor of manifolds satisfying the generalized axiom of spheres. This structure mostly resembles the structure of the curvature tensor of manifolds with the generalized axiom of planes.     

The Strong Thirteen Spheres Problem

The thirteen spheres problem asks if 13 equal-size non-overlapping spheres in three dimensions can simultaneously touch another sphere of the same size. This problem was the subject of the famous discussion between Isaac Newton and David Gregory in 1694. The problem was solved by Schütte and van der Waerden only in 1953. A natural extension of this problem is the strong thirteen-sphere problem (or the Tammes problem for 13 points), which calls for finding the maximum radius of and an arrangement for 13 equal-size non-overlapping spheres touching the unit sphere. In this paper, we give a solution of this long-standing open problem in geometry. Our computer-assisted proof is based on an enumeration of irreducible graphs.     

Volume-Minimizing Foliations on Spheres

The volume of a k-dimensional foliation in a Riemannian manifold Mⁿ is defined as the mass of the image of the Gauss map, which is a map from M to the Grassmann bundle of k-planes in the tangent bundle. Generalizing the construction by Gluck and Ziller (Comment. Math. Helv. 61 (1986), 177–192), ‘singular’ foliations by 3-spheres are constructed on round spheres S⁴ⁿ⁺³, as well as a singular foliation by 7-spheres on S¹⁵, which minimize volume within their respective relative homology classes. These singular examples, even though they are not homologous to the graph of a foliation, provide lower bounds for volumes of regular three-dimensional foliations of S⁴ⁿ⁺³ and regular seven-dimensional foliations of S¹⁵, since the double of these currents will be homologous to twice the graph of any smooth foliation by 3-manifolds.The second author was supported during this research by grants from the Universidade de Sāo Paulo, FAPESP Proc. 1999/02684-5, and Lehigh University, and thanks those institutions for enabling the collaboration involved in this work.Mathematics Subject Classifications (2000). 53C12, 53C38.     

Quadratic Interpolation on Spheres

Riemannian quadratics are C ¹ curves on Riemannian manifolds, obtained by performing the quadratic recursive deCastlejeau algorithm in a Riemannian setting. They are of interest for interpolation problems in Riemannian manifolds, such as trajectory-planning for rigid body motion. Some interpolation properties of Riemannian quadratics are analysed when the ambient manifold is a sphere or projective space, with the usual Riemannian metrics.     

The rate of convergence of the Walk on Spheres Algorithm

In this paper we examine the rate of convergence of one of the standard algorithms for emulating exit probabilities of Brownian motion, the Walk on Spheres (WoS) algorithm. We obtain a complete characterization of the rate of convergence of WoS in terms of the local geometry of a domain.     

单位球面上的等距延拓

该文研究了实赋范空间的单位球面上的等距算子延拓问题. 为此, 作者定义一个新的空间E^#, 称之为正齐性对偶空间, 并且研究了E^#上的一个新的拓扑σ(E^#, E). 从而, 作者就可以证明实赋范空间的单位球面上的一类满等距算子可以线性延拓到全空间上.     

Rigidity of Minimal Isometric Immersions of Spheres into Spheres

We show two specific uniqueness properties of a certain minimal isometric immersion from S3 into S6. This particular immersion has been extensively studied. We give the first uniqueness results for any such map within the full class of all minimal isometric immersion from S3(1) into S6( ). We also derive an explicit necessary and sufficient condition for linear rigidity of a general minimal isometric immersion from a sphere into a sphere.     

Isometric Stochastic Flows on Spheres

We consider isometric stochastic flows on the sphere S ^n–1 with the same one point motion. In particular, we will show that when n>3, the set of such flows with Brownian motion as one point motion can be represented by a cube in some Euclidean space.     

常曲率球面到单位球面的等距极小浸入与嵌入

本文主要估计了球面到单位球面的等距极小浸入的覆盖层数，从而导出一些有关嵌入的结果。同时，在本文证明过程中，给出了一个构造指定覆盖层数的等距极小浸入的方法．     

The Thirteen Spheres: A New Proof

The thirteen spheres problem, also known as the Gregory–Newton problem, is to determine the maximum number of three-dimensional spheres that can simultaneously touch a given sphere, where all the spheres have the same radius. The history of the problem goes back to a disagreement between Isaac Newton and David Gregory in 1694. Using a combination of harmonic analysis and linear programming it can be shown that the maximum cannot exceed 13, but in fact 13 is impossible. The standard proof that the maximum is 12 uses an ad hoc construction that does not appear to extend to higher dimensions. In this paper we describe a new proof that uses linear programming bounds and properties of spherical Delaunay triangulations.     

The Complexity of Gene Placement

We focus on algorithmic problems related to deriving gene locations on DNA sequences of closely related species by using comparative mapping data. Conventional genetic mapping generates intervals on the DNA sequence of given species for potential gene positions. The simultaneous analysis of gene intervals in related species, e.g., human and mouse, may eliminate some of the ambiguities and lead to better estimates of gene locations. We address the problem of eliminating the ambiguities in gene orders by means of minimizing the number of conserved regions among the species. This is equivalent to the problem of choosing gene coordinates (gene placement) that satisfy the genetic mapping constraints and minimize the breakpoint distance between genomes. We first show that the gene ordering problem is hard: there is no polynomial-time approximation scheme unless P = NP, even under the restrictions that: (1) the order of genes in one of species is known, or (2) at most two intervals overlap at any location on the map of any of the species. Then we provide two polynomial-time algorithms under restriction (1) above; the first approximates the problem within a factor of 3, and the second exactly solves the problem under the additional restriction that (3) no more than O((log n)/(log log n)) intervals overlap at a location on the map of any of the species. We also prove the tractability of the general problem when there is a single conserved region (i.e., when there exists a gene placement resulting in identical gene orders).     

The Infimum of the Energy of Unit Vector Fields on Odd-Dimensional Spheres

We construct a one-parameter family of unit smooth vector fieldsglobally defined on the sphere ^2k+1 for k 2, with energyconverging to the energy of the unit radial vector field, which isdefined on the complementary of two antipodal points. So we prove thatthe infimum of the energy of globally defined unit smooth vector fieldsis

Smash积的复杂度

给定任意一个有限维代数A,记其复杂度为C（A）.本文的主要结果是：如果有限维Hopf代数H和H是半单的,则对任意有限维H-模代数A,有C（A#H）=C（A）.利用此等式,可以计算一些代数的复杂度.     

The Complexity of Stratification Computation

This paper investigates the complexity of stratification computation for semialgebraic sets. An upper bound for the computation of canonical stratifications is given for a wide class of stratifying conditions called here admissible. For such conditions, the stratifying process is at most doubly exponential in the depth of the stratification. Usual conditions of regularity like Whitney conditions (a) and (b) or Bekka condition (C) are admissible. A useful criterion and tools are given in order to prove easily other admissibilities. Received February 15, 1995, and in revised form January 29, 1997 and May 6, 1997.