Cell Decompositions of the Projective Plane with Petrie Polygons of Constant Length

We study dual pairs of combinatorial face-to-face cell decompositions of the real projective plane P ² such that their canonically induced cell decompositions on the 2-sphere S ² form dual pairs of combinatorical types of convex polyhedra, and such that these dual pairs share two natural properties with those induced by dual pairs of Platonic solids: (1) Every Petrie polygon is a finite simple closed polygon of length 2(n-1) for some fixed n. (2) Every pair of Petrie polygons has precisely two common edges. Such pairs of face-to-face cell decompositions of the projective plane are in one-to-one correspondence with n-element pseudoline arrangements. We study in particular those dual pairs of cell decompositions in which has only 3-valent vertices, i.e., via the above one-to-one correspondence: p ₃-maximal pseudoline arrangements. A p ₃ -maximal pseudoline arrangement with n elements in turn determines a neighborly 2-manifold with Euler characteristic χ = n(7-n)/6, and vice versa, this neighborly 2-manifold uniquely determines its generating p ₃ -maximal pseudoline arrangement. We provide new inductive constructions for finding infinite example classes of p ₃-maximal pseudoline arrangements from small existing ones, we describe an algorithm for generating them, we provide a complete list of existence up to n = 40, and we discuss their properties. Received July 18, 1996, and in revised form October 28, 1996.     

Multitriangulations, Pseudotriangulations and Primitive Sorting Networks

We study the set of all pseudoline arrangements with contact points which cover a given support. We define a natural notion of flip between these arrangements and study the graph of these flips. In particular, we provide an enumeration algorithm for arrangements with a given support, based on the properties of certain greedy pseudoline arrangements and on their connection with sorting networks. Both the running time per arrangement and the working space of our algorithm are polynomial. As the motivation for this work, we provide in this paper a new interpretation of both pseudotriangulations and multitriangulations in terms of pseudoline arrangements on specific supports. This interpretation explains their common properties and leads to a natural definition of multipseudotriangulations, which generalizes both. We study elementary properties of multipseudotriangulations and compare them to iterations of pseudotriangulations.     

A new approach to constructing exponentially many nonisomorphic nonorientable triangular embeddings of complete graphs

We prove a theorem that for an integer s?0, if 12s+7 is a prime number, then the number of nonisomorphic face 3-colorable nonorientable triangular embeddings of K_n, where n=(12s+7)(6s+7), is at least . By some number-theoretic arguments there are an infinite number of integers s satisfying the hypothesis of the theorem. The theorem is the first known example of constructing at least 2^αn?+o(n?), ?>1, nonisomorphic nonorientable triangular embeddings of K_n for n=6t+1, . To prove the theorem, we use a new approach to constructing nonisomorphic triangular embeddings of complete graphs. The approach combines a cut-and-paste technique and the index one current graph technique. A new connection between Steiner triple systems and constructing triangular embeddings of complete graphs is given.     

Two conjectures of Grünbaum on arrangements of curves

We prove the following two conjectures of Grünbaum on arrangements of curves in the Euclidean plane: (a) There is no arrangement of n curves such that 4n - 4<f₂(A)<5n - 12. (b) There is no digon-free arrangement of n curves (n?36) such that 4n - 4<f₂(A)<5n - 7. (f₂(A) denotes the number of faces of the arrangement A.) Generalizing (a). we obtain: (c) For each k there is an integer n₀ (depending on k) such that no arrangement of n curves (n ? n₀) satisfies: kn-2k+4<f₂(A)<(k+1)n-k(k-1).     

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.     

Testing Graph Isotopy on Surfaces

We investigate the following problem: Given two embeddings G ₁ and G ₂ of the same abstract graph G on an orientable surface S, decide whether G ₁ and G ₂ are isotopic; in other words, whether there exists a continuous family of embeddings between G ₁ and G ₂. We provide efficient algorithms to solve this problem in two models. In the first model, the input consists of the arrangement of G ₁ (resp., G ₂) with a fixed graph cellularly embedded on S; our algorithm is linear in the input complexity, and thus, optimal. In the second model, G ₁ and G ₂ are piecewise-linear embeddings in the plane, minus a finite set of points; our algorithm runs in O(n ^3/2logn) time, where n is the complexity of the input. The graph isotopy problem is a natural variation of the homotopy problem for closed curves on surfaces and on the punctured plane, for which algorithms have been given by various authors; we use some of these algorithms as a subroutine. As a by-product, we reprove the following mathematical characterization, first observed by Ladegaillerie (Topology 23:303–311, 1984): Two graph embeddings are isotopic if and only if they are homotopic and congruent by an oriented homeomorphism.     

The brick polytope of a sorting network

The associahedron is a polytope whose graph is the graph of flips on triangulations of a convex polygon. Pseudotriangulations and multitriangulations generalize triangulations in two different ways, which have been unified by Pilaud & Pocchiola in their study of flip graphs on pseudoline arrangements with contacts supported by a given sorting network.In this paper, we construct the brick polytope of a sorting network, obtained as the convex hull of the brick vectors associated to each pseudoline arrangement supported by the network. We combinatorially characterize the vertices of this polytope, describe its faces, and decompose it as a Minkowski sum of matroid polytopes.Our brick polytopes include Hohlweg & Lange’s many realizations of the associahedron, which arise as brick polytopes for certain well-chosen sorting networks. We furthermore discuss the brick polytopes of sorting networks supporting pseudoline arrangements which correspond to multitriangulations of convex polygons: our polytopes only realize subgraphs of the flip graphs on multitriangulations and they cannot appear as projections of a hypothetical multiassociahedron.     

Steiner Triple Systems,Pinched Surfaces,and Complete Multigraphs

We consider complete multigraphs \({K_n^m}\) on n vertices with every pair joined by m edges. We embed these graphs to triangulate \({S_n^k}\) , a pinched surface with n pinch points each having k sheets. These embeddings have a vertex at each pinch point and any two sheets at a pinch point have the same number of edges. Moreover, we want to 2m-color the faces such that each color class is a Steiner triple system. These embeddings generalize in two ways biembeddings of Steiner triple systems, the case m =  1, k =  1 of simple graphs in surfaces without pinch points.     

Quaternion algebras, Heegner points and the arithmetic of Hida families

Given a newform f, we extend Howard??s results on the variation of Heegner points in the Hida family of f to a general quaternionic setting. More precisely, we build big Heegner points and big Heegner classes in terms of compatible families of Heegner points on towers of Shimura curves. The novelty of our approach, which systematically exploits the theory of optimal embeddings, consists in treating both the case of definite quaternion algebras and the case of indefinite quaternion algebras in a uniform way. We prove results on the size of Neková???s extended Selmer groups attached to suitable big Galois representations and we formulate two-variable Iwasawa main conjectures both in the definite case and in the indefinite case. Moreover, in the definite case we propose refined conjectures à la Greenberg on the vanishing at the critical points of (twists of) the L-functions of the modular forms in the Hida family of f living on the same branch as f.     

Reconstruction of quasi developable surfaces from ribbon curves

This paper deals with the acquisition and reconstruction of physical surfaces by mean of a ribbon device equipped with micro-sensors, providing geodesic curves running on the surface. The whole process involves the reconstruction of these 3D ribbon curves together with their global treatment so as to produce a consistent network for the geodesic surface interpolation by filling methods based on triangular Coons-like approaches. However, the ribbon curves follow their own way, subdividing thus the surface into arbitrary n-sided patches. We present here a method for the reconstruction of quasi developable surfaces from such n-sided curvilinear boundary curves acquired with the ribbon device.     

Enumerating reflexible 2-cell embeddings of connected graphs

Two 2-cell embeddings:X → S and j:X → S of a connected graph X into a closed orientable surface S are congruent if there are an orientation-preserving surface homeomorphism h on S and a graph automorphism γ of X such that h = γj.A 2-cell embedding:X → S of a graph X into a closed orientable surface S is described combinatorially by a pair(X;ρ) called a map,where ρ is a product of disjoint cycle permutations each of which is the permutation of the darts of X initiated at the same vertex following the orientation of S.The mirror image of a map(X;ρ) is the map(X;ρ 1),and one of the corresponding embeddings is called the mirror image of the other.A 2-cell embedding of X is reflexible if it is congruent to its mirror image.Mull et al.[Proc Amer Math Soc,1988,103:321-330] developed an approach for enumerating the congruence classes of 2-cell embeddings of graphs into closed orientable surfaces.In this paper we introduce a method for enumerating the congruence classes of reflexible 2-cell embeddings of graphs into closed orientable surfaces,and apply it to the complete graphs,the bouquets of circles,the dipoles and the wheel graphs to count their congruence classes of reflexible or nonreflexible(called chiral) embeddings.     

5-Chromatic even triangulations on surfaces

A triangulation is said to be even if each vertex has even degree. It is known that every even triangulation on any orientable surface with sufficiently large representativity is 4-colorable [J. Hutchinson, B. Richter, P. Seymour, Colouring Eulerian triangulations, J. Combin. Theory, Ser. B 84 (2002) 225-239], but all graphs on any surface with large representativity are 5-colorable [C. Thomassen, Five-coloring maps on surfaces, J. Combin Theory Ser. B 59 (1993) 89-105]. In this paper, we shall characterize 5-chromatic even triangulations with large representativity, which appear only on nonorientable surfaces.     

Proper holomorphic embeddings of finitely connected planar domains into ℂ n

In this paper we consider proper holomorphic embeddings of finitely connected planar domains into ? ⁿ that approximate given proper embeddings on smooth curves. As a side result we obtain a tool for approximating a $\mathcal{C}^{\infty}$ diffeomorphism on a polynomially convex set in ? ⁿ by an automorphism of ? ⁿ that satisfies some additional properties along a real embedded curve.     

Computing parallel curves on parametric surfaces

Generating parallel curves on parametric surfaces is an important issue in many industrial settings. Given an initial curve (called the base curve or generator) on a parametric surface, the goal is to obtain curves on the surface that are parallel to the generator. By parallel curves we mean curves that are at a given distance from the generator, where distance is measured point-wise along certain characteristic curves (on the surface) orthogonal to the generator. Except for a few particular cases, computing these parallel curves is a very difficult and challenging problem. In fact, only partial, incomplete solutions have been reported so far in the literature. In this paper we introduce a simple yet efficient method to fill this gap. In clear contrast with other existing techniques, the most important feature of our method is its generality: it can be successfully applied to any differentiable parametric surface and to any kind of characteristic curves on surfaces. To evaluate our proposal, some illustrative examples (not addressed with previous methods) for the cases of section, vector-field, and geodesic parallels are discussed. Our experimental results show the excellent performance of the method even for the complex case of NURBS surfaces.     

Onk-sets in arrangements of curves and surfaces

We extend the notion ofk-sets and (≤k)-sets (see [3], [12], and [19]) to arrangements of curves and surfaces. In the case of curves in the plane, we assume that each curve is simple and separates the plane. Ak-point is an intersection point of a pair of the curves which is covered by exactlyk interiors of (or half-planes bounded by) other curves; thek-set is the set of allk-points in such an arrangement, and the (≤k)-set is the union of allj-sets, forj≤k. Adapting the probabilistic analysis technique of Clarkson and Shor [13], we obtain bounds that relate the maximum size of the (≤k)-set to the maximum size of a 0-set of a sample of the curves. Using known bounds on the size of such 0-sets we obtain asympotically tight bounds for the maximum size of the (≤k)-set in the following special cases: (i) If each pair of curves intersect at most twice, the maximum size is Θ(nkα(nk)). (ii) If the curves are unbounded arcs and each pair of them intersect at most three times, then the maximum size is Θ(nkα(n/k)). (iii) If the curves arex-monotone arcs and each pair of them intersect in at most some fixed numbers of points, then the maximum size of the (≤k)-set is Θ(k ²λ _s (nk)), where λ _s (m) is the maximum length of (m,s)-Davenport-Schinzel sequences. We also obtain generalizations of these results to certain classes of surfaces in three and higher dimensions. Finally, we present various applications of these results to arrangements of segments and curves, high-order Voronoi diagrams, partial stabbing of disjoint convex sets in the plane, and more. An interesting application yields andO(n logn) bound on the expected number of vertically visible features in an arrangement ofn horizontal discs when they are stacked on top of each other in random order. This in turn leads to an efficient randomized preprocessing ofn discs in the plane so as to allow fast stabbing queries, in which we want to report all discs containing a query point. Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the NCRD—the Israeli National Council for Research and Development-and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences.     

Triangular embeddings of complete graphs (neighborly maps) with 12 and 13 vertices

In this paper, we describe the generation of all nonorientable triangular embeddings of the complete graphs K₁₂ and K₁₃. (The 59 nonisomorphic orientable triangular embeddings of K₁₂ were found in 1996 by Altshuler, Bokowski, and Schuchert, and K₁₃ has no orientable triangular embeddings.) There are 182,200 nonisomorphic nonorientable triangular embeddings for K₁₂, and 243,088,286 for K₁₃. Triangular embeddings of complete graphs are also known as neighborly maps and are a type of twofold triple system. We also use methods of Wilson to provide an upper bound on the number of simple twofold triple systems of order n, and thereby on the number of triangular embeddings of K_n. We mention an application of our results to flexibility of embedded graphs. © 2005 Wiley Periodicals, Inc. J Combin Designs     

On a special case of the intersection of quadric and cubic surfaces

The intersection curve between two surfaces in three-dimensional real projective space RP³ is important in the study of computer graphics and solid modelling. However, much of the past work has been directed towards the intersection of two quadric surfaces. In this paper we study the intersection curve between a quadric and a cubic surface and its projection onto the plane at infinity. Formulas for the plane and space curves are given for the intersection of a quadric and a cubic surface. A family of cubic surfaces that give the same space curve when we intersect them with a quadric surface is found. By generalizing the methods in Wang et al. (2002) [6] that are used to parametrize the space curve between two quadric surfaces, we give a parametrization for the intersection curve between a quadric and a cubic surface when the intersection has a singularity of order 3.     

Proof of a conjecture of Burr,Grünbaum,and Sloane

We establish a duality principle for arrangements of pseudolines in the projective plane, and thereby prove the conjecture of Burr, Grünbaum, and Sloane that the solution

of the “orchard problem” for pseudoline arrangements and the solution t?(p) of the dual problem are equal.     

Classification of arrangements by the number of their cells

The possible pairs (n, f) of integers for which there are arrangements withn lines andf cells are determined. The pair (n, f) corresponds to an arrangement if and only if there is an integerk with 0≤k≤n?2 such that $$(n - k)(k + 1) + \left( {_2^k } \right) - \min \left\{ {n - k,\left( {_2^k } \right)} \right\} \leqslant f \leqslant (n - k)(k + 1) + \left( {_2^k } \right).$$      

Darboux transforms and spectral curves of Hamiltonian stationary Lagrangian tori

The multiplier spectral curve of a conformal torus f : T ² → S ⁴ in the 4-sphere is essentially (Bohle et al., Conformal maps from a 2-torus to the 4-sphere. arXiv:0712.2311) given by all Darboux transforms of f. In the particular case when the conformal immersion is a Hamiltonian stationary torus ${f: T^2 \to\mathbb{R}^4}$ in Euclidean 4-space, the left normal N : M → S ² of f is harmonic, hence we can associate a second Riemann surface: the eigenline spectral curve of N, as defined in Hitchin (J Differ Geom 31(3):627–710, 1990). We show that the multiplier spectral curve of a Hamiltonian stationary torus and the eigenline spectral curve of its left normal are biholomorphic Riemann surfaces of genus zero. Moreover, we prove that all Darboux transforms, which arise from generic points on the spectral curve, are Hamiltonian stationary whereas we also provide examples of Darboux transforms which are not even Lagrangian.