The geometry of a graph \(G\) embedded on a closed oriented surface \(S\) can be probed by counting the intersections of \(G\) with closed curves on \(S\). Of special interest is the map \(c \mapsto \mu_G(c)\) counting the minimum number of intersections between \(G\) and any curve freely homotopic to a given curve \(c\). Schrijver [On the uniqueness of kernels, 1992] calls \(G\) a kernel if for any proper graph minor \(H\) of \(G\) we have \(\mu_H \lt \mu_G\). Hence, \(G\) admits a minor \(H\) which is a kernel and such that \(\mu_G = \mu_H\). We show how to compute such a minor kernel of \(G\) in \(O(n^3 \log n)\) time where \(n\) is the number of edges of \(G\), and \(g \ge 2\) is the genus of \(S\). Our algorithm leverages a tight bound on the size of minimal bigons in a system of closed curves. It also relies on several subroutines of independent interest including the computation of the area enclosed by a curve and a test of simplicity for the lift of a curve in the universal covering of \(S\).

Given a weighted, undirected graph G cellularly embedded on a topological surface S, we describe algorithms to compute the second shortest and third shortest closed walks of G that are neither homotopically trivial in S nor homotopic to the shortest non-trivial closed walk or to each other. Our algorithms run in O (n2 log n ) time for the second shortest walk and in O (n3) time for the third shortest walk. We also show how to reduce the running time for the second shortest homotopically non-trivial closed walk to O (n log n ) when both the genus and the number of boundaries are fixed.

Abstract. We provide a combinatorial and self-contained proof of a result following from G. Besson [ Ann. Inst. Fourier, 30 (1980), pp. 109–128] and Y. Colin de Verdière [ Ann. Sci. Éc. Norm. Supér., 20 (1987), pp. 599–615] that for all graphs [Formula: see text] embedded on a surface [Formula: see text], the Colin de Verdière parameter [Formula: see text] is upper bounded by [Formula: see text].

Consider a weighted, undirected graph cellularly embedded on a topological surface. The function assigning to each free homotopy class of closed curves the length of a shortest cycle within this homotopy class is called the marked length spectrum. The (unmarked) length spectrum is obtained by just listing the length values of the marked length spectrum in increasing order. In this paper, we describe algorithms for computing the (un)marked length spectra of graphs embedded on the torus. More specifically, we preprocess a weighted graph of complexity $n$ in time $O(n^2 \log \log n)$ so that, given a cycle with $\ell$ edges representing a free homotopy class, the length of a shortest homotopic cycle can be computed in $O(\ell+\log n)$ time. Moreover, given any positive integer $k$, the first $k$ values of its unmarked length spectrum can be computed in time $O(k \log n)$. Our algorithms are based on a correspondence between weighted graphs on the torus and polyhedral norms. In particular, we give a weight independent bound on the complexity of the unit ball of such norms. As an immediate consequence we can decide if two embedded weighted graphs have the same marked spectrum in polynomial time. We also consider the problem of comparing the unmarked spectra and provide a polynomial time algorithm in the unweighted case and a randomized polynomial time algorithm otherwise.

A result due to Burago and Zalgaller states that every orientable polyhedral surface, one that is obtained by gluing Euclidean polygons, has an isometric piecewise linear (PL) embedding into Euclidean space 𝔼³. A flat torus, resulting from the identification of the opposite sides of a Euclidean parallelogram, is a simple example of polyhedral surface. In a first part, we adapt the proof of Burago and Zalgaller, which is partially constructive, to produce PL isometric embeddings of flat tori. In practice, the resulting embeddings have a huge number of vertices, moreover distinct for every flat torus. In a second part, based on another construction of Zalgaller and on recent works by Arnoux et al., we exhibit a universal triangulation with 5974 triangles which can be embedded linearly on each triangle in order to realize the metric of any flat torus.

In this paper we prove that the problem of deciding contractibility of an arbitrary closed curve on the boundary of a 3-manifold is in NP. We emphasize that the manifold and the curve are both inputs to the problem. Moreover, our algorithm also works if the curve is given as a compressed word. Previously, such an algorithm was known for simple (non-compressed) curves, and, in very limited cases, for curves with self-intersections. Furthermore, our algorithm is fixed-parameter tractable in the complexity of the input 3-manifold. As part of our proof, we obtain new polynomial-time algorithms for compressed curves on surfaces, which we believe are of independent interest. We provide a polynomial-time algorithm which, given an orientable surface and a compressed loop on the surface, computes a canonical form for the loop as a compressed word. In particular, contractibility of compressed curves on surfaces can be decided in polynomial time; prior published work considered only constant genus surfaces. More generally, we solve the following normal subgroup membership problem in polynomial time: given an arbitrary orientable surface, a compressed closed curve γ, and a collection of disjoint normal curves Δ, there is a polynomial-time algorithm to decide if γ lies in the normal subgroup generated by components of Δ in the fundamental group of the surface after attaching the curves to a basepoint.

The geometric intersection number of a curve on a surface is the minimal number of self-intersections of any homotopic curve, i.e., of any curve obtained by continuous deformation. Given a curve c represented by a closed walk of length at most ℓ on a combinatorial surface of complexity n , we describe simple algorithms to (1) compute the geometric intersection number of c in O ( n + ℓ 2 ) time, (2) construct a curve homotopic to c that realizes this geometric intersection number in O ( n +ℓ 4 ) time, and (3) decide if the geometric intersection number of c is zero, i.e., if c is homotopic to a simple curve, in O ( n +ℓ log ℓ) time. The algorithms for (2) and (3) are restricted to orientable surfaces, but the algorithm for (1) is also valid on non-orientable surfaces. To our knowledge, no exact complexity analysis had yet appeared on those problems. An optimistic analysis of the complexity of the published algorithms for problems (1) and (3) gives at best a O ( n + g 2 ℓ 2 ) time complexity on a genus g surface without boundary. No polynomial time algorithm was known for problem (2) for surfaces without boundary. Interestingly, our solution to problem (3) provides a quasi-linear algorithm to a problem raised by Poincaré more than a century ago. Finally, we note that our algorithm for problem (1) extends to computing the geometric intersection number of two curves of length at most ℓ in O ( n + ℓ 2 ) time.

Let $S_{g,n}$ be a surface of genus $g $ with $n$ marked points. Let $X$ be a complete hyperbolic metric on $S_{g,n}$ with $n$ cusps. Every isotopy class $[γ]$ of a closed curve $γ\in π_{1}(S_{g,n})$ contains a unique closed geodesic on $X$. Let $\ell_γ(X)$ denote the hyperbolic length of the geodesic representative of $γ$ on $X$. In this paper, we study the asymptotic growth of the lengths of closed curves of a fixed topological type on $S_{g,n}.$ As an application, one can obtain the asymptotics of the growth of $s^{k}_{X}(L)$, the number of closed curves of length $\leq L$ on $X$ with at most $k$ self-intersections. We also discuss properties of random pants decomposition of large length on $X$. Both these results are based on ergodic properties of the earthquake flow on a natural bundle over the moduli space $\mathcal{M}_{g,n}$ of hyperbolic surfaces of genus $g$ with $n$ cusps.

Let G be a graph cellularly embedded in a surface S. Given two closed walks c and d in G, we take advantage of the RAM model to describe linear time algorithms to decide if c and d are homotopic in S, either freely or with fixed base point. After O(|G|) time preprocessing independent of c and d, our algorithms answer the homotopy test in O(|c| + |d|) time, where |G|, |c| and |d| are the respective numbers of edges of G, c and d. These results were previously announced by Dey and Guha (1999). Their approach was based on small cancellation theory from combinatorial group theory. However, several flaws in their algorithms make their approach fail, leaving the complexity of the homotopy test problem still open. We present a geometric approach, based on previous works by Colin de Verdière and Erickson, that provides optimal homotopy tests.

Let G be a graph cellularly embedded on a surface $\mathcal{S}$. We consider the problem of determining whether G contains a cycle (i.e., a closed walk without repeated vertices) of a certain topological type in $\mathcal{S}$. We show that the problem can be answered in linear time when the topological type is one of the following: contractible, noncontractible, or nonseparating. In each case, we obtain the same time complexity if we require the cycle to contain a given vertex. On the other hand, we prove that the problem is NP-complete when considering separating or splitting cycles. We also show that deciding the existence of a separating or a splitting cycle of length at most k is fixed-parameter tractable with respect to k plus the genus of the surface.

Let G be an unweighted graph of complexity n cellularly embedded in a surface (orientable or not) of genus g. We describe improved algorithms to compute (the length of) a shortest non-contractible and a shortest non-separating cycle of G.

Let D be a weighted directed graph cellularly embedded in a surface of genus g, orientable or not, possibly with boundary. We describe algorithms to compute a shortest non-contractible and a shortest surface non-separating cycle in D. This generalizes previous results that only dealt with undirected graphs.

The Fréchet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other, without backtracking. We propose a natural extension of Fréchet distance to more general metric spaces, which requires the leash itself to move continuously over time. For example, for curves in the punctured plane, the leash cannot pass through or jump over the obstacles ("trees"). We describe a polynomial-time algorithm to compute the homotopic Fréchet distance between two given polygonal curves in the plane minus a given set of obstacles, which are either points or polygons.

We consider the problem of finding a shortest cycle (freely) homotopic to a given simple cycle on a compact, orientable surface. For this purpose, we use a pants decomposition of the surface: a set of disjoint simple cycles that cut the surface into pairs of pants (spheres with three holes). We solve this problem in a framework where the cycles are closed walks on the vertex-edge graph of a combinatorial surface that may overlap but do not cross. We give an algorithm that transforms an input pants decomposition into another homotopic pants decomposition that is optimal : each cycle is as short as possible in its homotopy class. As a consequence, finding a shortest cycle homotopic to a given simple cycle amounts to extending the cycle into a pants decomposition and to optimizing it: the resulting pants decomposition contains the desired cycle. We describe two algorithms for extending a cycle to a pants decomposition. All algorithms in this article are polynomial, assuming uniformity of the weights of the vertex-edge graph of the surface.

All in-text\treferences\tunderlined\tin\tblue\tare\tlinked\tto\tpublications\ton\tResearchGate, letting you\taccess\tand\tread\tthem\timmediately.

Every compact orientable boundaryless surface /spl Mscr/ can be cut along simple loops with a common point /spl upsi//sub 0/, pairwise disjoint except at /spl upsi//sub 0/, so that the resulting surface is a topological disk; such a set of loops is called a fundamental system of loops for /spl Mscr/. The resulting disk is a polygon in which the edges are pairwise identified on the surface; it is called a polygonal schema Assuming that /spl Mscr/ is triangulated, and that each edge has a given length, we are interested in a shortest (or optimal) system homotopic to a given one, drawn on the vertex-edge graph of /spl Mscr/. We prove that each loop of such an optimal system is a shortest loop among all simple loops in its homotopy class. We give a polynomial (under some reasonable assumptions) algorithm to build such a system. As a byproduct, we get a polynomial algorithm to compute a shortest simple loop homotopic to a given simple loop.

A closed orientable surface of genus $g$ can be obtained by appropriat e identification of pairs of edges of a $4g$-gon (the polygonal schema). The identified edges form $2g$ loops on the surface, that are disjoint except for their common end-point. These loops are generators of both the fundamental group and the homology group of the surface. The inverse problem is concerned with finding a set of $2g$ loops on a triangulated surface, such that cutting the surface along these loops yields a (canonical) polygonal schema. We present two optimal algorithms for this inverse problem. Both algorithms have been implemented using the CGAL polyhedron data structure.

Many real-world polygonal surfaces contain topological singularities that represent a challenge for processes such as simplification, compression, and smoothing. We present an algorithm that removes singularities from nonmanifold sets of polygons to create manifold (optionally oriented) polygonal surfaces. We identify singular vertices and edges, multiply singular vertices, and cut through singular edges. In an optional stitching operation, we maintain the surface as a manifold while joining boundary edges. We present two different edge stitching strategies, called pinching and snapping. Our algorithm manipulates the surface topology and ignores physical coordinates. Except for the optional stitching, the algorithm has a linear complexity and requires no floating point operations. In addition to introducing new algorithms, we expose the complexity (and pitfalls) associated with stitching. Finally, several real-world examples are studied.

We introduce a method for extracting skeletal curves from an unorganized collection of scattered data points lying on a surface. These curves may have a tree like structure to capture branching shapes such as blood vessels. The skeletal curves can be used for different applications ranging from surface reconstruction to object recognition.

In this paper we introduce the Progressive Forest Split (PFS) representation, a new adaptive refinement scheme for storing and transmitting manifold triangular meshes in progressive and highly compressed form. As in the Progressive Mesh (PM) method of Hoppe, a triangular mesh is represented as a low resolution polygonal model followed by a sequence of refinement operations, each one specifying how to add triangles and vertices to the previous level of detail to obtain a new level. The PFS format shares with PM and other refinement schemes the ability to smoothly interpolate between consecutive levels of detail. However, it achieves much higher compression ratios than PM by using a more complex refinement operation which can, at the expense of reduced granularity, be encoded more efficiently. A forest split operation doubling the number n of triangles of a mesh requires a maximum of approximately 3:5n bits to represent the connectivity changes, as opposed to approximately #5 + log 2 #n## n bits in PM. We describe

Many real world polygonal surfaces contain topological singularities that represent a challenge for processes such as simplification, compression, smoothing, etc. We present an algorithm for removing such singularities, thus converting non manifold sets of polygons to manifold polygonal surfaces (orientable if necessary). We identify singular vertices and edges, multiply singular vertices, and cut through singular edges. In an optional stitching phase, we join surface boundary edges that were cut, or whose endpoints are sufficiently close, while guaranteeing that the surface is a manifold. We study two different stitching strategies called "edge pinching" and "edge snapping"; when snapping, special care is required to avoid re-creating singularities. The algorithm manipulates the polygon vertex indices (surface topology) and essentially ignores vertex coordinates (surface geometry). Except for the optional stitching, the algorithm has a linear complexity in the number of vertices edges and faces, and require no floating point operation.

The virtual-reality modeling language (VRML) is rapidly becoming the standard file format for transmitting three-dimensional (3-D) virtual worlds across the Internet. Static and dynamic descriptions of 3-D objects, multimedia content, and a variety of hyperlinks can be represented in VRML files. Both VRML browsers and authoring tools for the creations of VRML files are widely available for several different platforms. In this paper, we describe the topologically assisted geometric compression technology included in our proposal for the VRML compressed binary format. This technology produces significant reduction of file sizes and, subsequently, of the time required for transmission of such filed across the Internet. Compression ratios of 50:1 or more are achieved for large models. The proposal also includes a binary encoding to create compact, rapidly parsable binary VRML files. The proposal is currently being evaluated by the Compressed Binary Format Working Group of the VRML consortium as a possible extension of the VRML standard. In the topologically assisted compression scheme, a polyhedron is represented using two interlocking trees: a spanning tree of vertices and a spanning tree of triangles. The connectivity information represented in other compact schemes, such as triangular strips and generalized triangular meshes, can be directly derived from this representation. Connectivity information for large models is compressed with storage requirements approaching one bit per triangle. A variable-length, optionally lossy compression technique is used for vertex positions, normals, colors, and texture coordinates. The format supports all VRML property binding conventions.

A new technique is presented for computing continuous shape transformations between polyhedral objects. The correspondence and the interpolation problems are considered jointly as we construct and process on sampling polyhedral meshes of the objects. The approach is adapted to objects that are star-shaped around an axis. The process gives the animator a high level control over the shape transformation by providing natural specification and interaction. © 1997 John Wiley & Sons, Ltd.