How To Morph Graphs On The Torus - University Of Illinois .

1y ago
2 Views
1 Downloads
1.71 MB
20 Pages
Last View : 23d ago
Last Download : 2m ago
Upload by : Madison Stoltz
Transcription

How to Morph Graphs on the TorusErin Wolf Chambers†Jeff Erickson‡Patrick Lin‡Salman Parsa†Abstractfirst algorithm to morph graphs on any higher-genussurface. In fact, it is the first algorithm to computeWe present the first algorithm to morph graphs on the torus.any form of isotopy between surface graphs; existingGiven two isotopic essentially 3-connected embeddings of thealgorithms to test whether two graphs on the same surfacesame graph on the Euclidean flat torus, where the edges in bothare isotopic are non-constructive [29]. Our algorithmdrawings are geodesics, our algorithm computes a continuousoutputs a morph consisting of O(n) steps; within each step,deformation from one drawing to the other, such that all edgesall vertices move along parallel geodesics at (different)are geodesics at all times. Previously even the existence ofconstant speeds, and all edges remain geodesics (“straight1 ω/2such a morph was not known. Our algorithm runs in O(n)line segments”). Our algorithm runs in O(n1 ω/2 ) time; thetime, where ω is the matrix multiplication exponent, and therunning time is dominated by repeatedly solving a linearcomputed morph consists of O(n) parallel linear morphing steps.system encoding a natural generalization of Tutte’s springExisting techniques for morphing planar straight-line graphs doembedding theorem.not immediately generalize to graphs on the torus; in particular,Cairns’ original 1944 proof and its more recent improvements relyon the fact that every planar graph contains a vertex of degree 1.1 Prior Results (and Why They Don’t Generalize).at most 5. Our proof relies on a subtle geometric analysis of Cairns [20, 21] was the first to prove the existence of6-regular triangulations of the torus. We also make heavy use of a straight-line continuous deformation between any twoa natural extension of Tutte’s spring embedding theorem to torus isomorphic planar straight-line triangulations. A long seriesof later works, culminating in papers by Alamdari et al. [1]graphs.1IntroductionComputing a morph between two given geometric objectsis a fundamental problem, with applications to questionsin graphics, animation, and modeling. In general, the goalis twofold: ensure the morphs are as low complexity aspossible, and ensure that the intermediate objects retainthe same high level structure throughout the morph.Morphs between planar drawings are well studiedin the topology, graph drawing, and computer graphicsliterature, with many variants. A morph between twoplanar straight-line embeddings Γ0 and Γ1 of the sameplanar graph is a continuous family of planar embeddingsΓ t parametrized by time, starting at Γ0 and ending at Γ1 . Inthe most common formulation, all edges must be straightline segments at all times during the morph; there are thenmany variables of how to optimize the morph.In this paper, we consider the more general settingof morphs between two isotopic embeddings of the samegraph on the flat torus. To our knowledge, ours is theResearch partially supported by NSF grants CCF-1408763, CCF1614562, DBI-1759807, and CCF-1907612. Portions of this work weredone while the second author was visiting Utrecht University. No animalswere harmed in the making of this paper.†Saint Louis University‡University of Illinois, Urbana-Champaignand Kleist et al. [54], improved and generalized Cairns’argument to apply to arbitrary planar straight-line graphs,to produce morphs with polynomial complexity, and toderive efficient algorithms for computing those morphs.(For a more detailed history of these results, we refer thereader to Alamdari et al. [1] and Roselli [76].) Cairns’inductive argument and its successors fundamentally relyon two simple observations: (1) Every planar graph hasat least one vertex of degree at most five, and (2) Everypolygon with at most five vertices has at least one vertexin its visibility kernel. Thus, every planar straight-linegraph contains at least one vertex that can be collapsed toone of its neighbors while preserving the planarity of theembedding.Unfortunately, the first of these observations fails forgraphs on the torus; it is easy to construct a triangulationof the torus in which every vertex has degree 6. Moreover,not every star-shaped hexagon has a vertex in its visibilitykernel. Thus, it is no longer immediate that in any geodesictoroidal triangulation, one can move a vertex to one of itsneighbors while maintaining a proper geodesic embedding.(Indeed, the fact that we can actually collapse such an edgeis the main topic of Section 4.)Floater and Gotsman [42] described an alternativemethod for morphing planar triangulations using a generalization of Tutte’s spring-embedding theorem [84]. Everyinterior vertex in a planar triangulation can be expressedCopyright 2021 by SIAMUnauthorized reproduction of this article is prohibited

as a convex combination of its neighbors. Floater and Gotsman’s morph linearly interpolates between the coefficientsof these convex combinations; Tutte’s theorem implies thatat all times, the interpolated coordinates are consistent witha proper straight-line embedding. Gotsman and Surazhsky later generalized Floater and Gotsman’s technique toarbitrary planar straight-line graphs [47, 80, 81].At its core, Floater and Gotsman’s algorithm relieson the fact that the system of linear equations expressingvertices as convex combinations of their neighbors hasfull rank. An analogous system of equations describesequilibrium embeddings of graphs on the torus [38, 46];however, for graphs with n vertices, this linear system has2n equations over 2n variables (the vertex coordinates),but its rank is only 2n 2. If the linear system happens tohave a solution, that solution is consistent with a properembedding [28,32,46,62]; unfortunately, the system is notalways solvable.When the coefficients associated with each edge aresymmetric, the linear system has a two-dimensional setof solutions, which correspond to proper embeddingsthat differ only by translation. (See our Theorem 2.1below.) Thus, if two given triangulations can both bedescribed by symmetric coefficients, linearly interpolatingthose coordinates yields an isotopy [30]. Otherwise,however, even if the initial and final coefficient vectorsare feasible, weighted averages of those coefficients mightnot be. Steiner and Fisher [79] modify the linear system byfixing one vertex, restoring full rank. However, while thesolution to this linear system always describes a geodesicdrawing of the graph, edges in that drawing can cross. Ineither setting, linearly interpolating the edge coefficientsdoes not yield a morph.Both of these approaches produce planar morphsthat require high numerical precision to describe exactly.Barerra-Cruz et al. [11] describe an algorithm to morphbetween two isomorphic weighted Schnyder drawings of thesame triangulation, each determined by a Schnyder woodtogether with an assignment of positive weights to thefaces. The resulting morph consists of O(n2 ) steps, whereafter each step, all vertices lie on a 6n 6n integer grid.The algorithm relies crucially on the fact that the set ofSchnyder woods of a planar triangulation is a distributivelattice [41]. Despite some initial progress by Barerra-Cruz[9], it is still an open question whether this algorithm canbe extended to arbitrary planar triangulations, or even toarbitrary planar straight-line graphs. Beyond that, it is alsonot clear whether this result can be extended to toroidalgraphs. Castelli Aleardi et al. [22] and Gonçalves andLévêque [45] describe natural generalizations of Schnyderwoods to graphs on the torus; however, the Schnyder woods(or 3-orientations) of a toroidal triangulation do not forma distributive lattice.Considerably less is known about morphing graphson higher-genus surfaces. Like earlier planar morphingalgorithms, our algorithm follows the same inductivestrategy as several earlier algorithms for transformingcombinatorial embeddings into geodesic embeddings onthe torus [55,65,66]. Our algorithm most closely resemblesan algorithm of Kocay et al. [55], which transforms anyessentially 3-connected toroidal embedding into an isotopicgeodesic embedding, by repeatedly collapsing vertices withdegree at most 5 until the embedding becomes a 6-regulartriangulation.1.2 Our Results. We begin by reviewing relevant definitions and background in Section 2. Most importantly, wereview a natural generalization of Tutte’s spring embeddingtheorem [84] to graphs on the flat torus, first proved byY. Colin de Verdière [28]; see Theorem 2.1. We present atechnical overview of our contributions in Section 3, deferring details to later sections for clarity.Like many previous planar morphing papers, most ofour paper is devoted to computing pseudomorphs betweentriangulations. A pseudomorph is a continuous deformationin which vertices are allowed to coincide during the motionbut edges are not allowed to cross. Our pseudomorphalgorithm uses two different operations that reduce thecomplexity of the graph: direct collapses, which moveone vertex to one of its neighbors, and spring collapses,which increase the weight of one edge to infinity whilemaintaining an equilibrium embedding, as described byTheorem 2.1. The heart of our result is a novel analysis of6-regular toroidal triangulations in Section 4, which impliesthat every non-trivial toroidal triangulation contains at leastone edge that can be directly collapsed without introducingany crossings. We regard this analysis as the main technicalcontribution of our paper. We describe and analyze springcollapses in Section 5, again relying on Theorem 2.1. Wedescribe and analyze the base case of our pseudomorphalgorithm in Section 6: a special class of triangulations wecall zippers, where every vertex is incident to a loop.In Section 7, we show that a mild generalization oftechniques from Alamdari et al. [1] can be used to perturbour pseudomorph into a proper morph; this perturbationtechnique gives us our final morphing algorithm for triangulations. Finally, in Section 8, we describe a simplereduction from morphing essentially 3-connected geodesictoroidal embeddings to morphing triangulations, again using Theorem 2.1. We conclude in Section 9 with some openproblems and future directions to consider.2Background and Definitions2.1 The Flat Torus. The (square) flat torus T is themetric space obtained by identifying opposite sides of theCopyright 2021 by SIAMUnauthorized reproduction of this article is prohibited

unit square [0, 1]2 in the Euclidean plane via (x, 0) (x, 1)and (0, y) (1, y). See Figure 2.1. Equivalently, T is thequotient space T R2 /Z2 , obtained by identifying everypair of points whose x- and y-coordinates differ by integers.The function π: R2 T defined by π(x, y) (x mod 1,y mod 1) is called the covering map or projection map.A geodesic in T is the projection of any line segmentin R2 ; geodesics are the natural analogues of “straight linesegments” on the flat torus.1 We emphasize that a geodesicis not necessarily the shortest path between its endpoints;indeed, there are infinitely many geodesics between anytwo points on T. A closed geodesic in T is any geodesicwhose endpoints coincide; the two ends of any closedgeodesic are locally collinear.2.2 Toroidal Embeddings. Geodesic toroidal drawingsare the natural generalizations of straight-line planargraphs to the flat torus. Formally, a geodesic toroidaldrawing Γ of a graph G is a mapping of vertices todistinct points of T and edges to non-intersecting geodesicsbetween their endpoints. Following standard usage intopology, we refer to any such drawing as embedding, toemphasize that edges do not cross.2A homotopy between two (not necessarily injective)drawings Γ0 and Γ1 of the same graph G is a continuous function H : [0, 1] G T where H(0, ) Γ0 and H(1, ) Γ1 . Acycle on T is contractible if it is homotopic to a single pointand non-contractible otherwise. A homotopy is an isotopyif each intermediate function H(t, ) is injective. In otherwords, an isotopy is a continuous family of embeddings(Γ t ) t [0,1] that interpolates between Γ0 and Γ1 . (Edges inthese intermediate embeddings Γ t are not required to begeodesics.)Two toroidal embeddings of the same graph need notbe isotopic, even if they have the same rotation system; seeFigure 2.1. A recent algorithm of É. Colin de Verdière andde Mesmay [29] can decide whether two toroidal drawingsof the same graph are isotopic in linear time; we describean arguably simpler linear-time algorithm in Appendix A.However, neither of these algorithms actually constructan isotopy if one exists; rather, they check whether the1Identifying opposite sides of any other parallelogram yields a differentflat torus. All flat tori are related by homeomorphisms induced by lineartransformations that map geodesics to geodesics, and therefore mapmorphs to morphs. Thus, our results automatically apply to embeddingson any flat torus. On the other hand, our results do not apply to geodesicembeddings on the standard torus of revolution in R3 ; geodesics on thatsurface have radically different behavior.2Formally, an embedding is a continuous injective map from the graph(as a topological space) to the torus T. We note that this usage differsfrom standard terminology in many other graph drawing papers, where“embedding” refers to either a homeomorphism class of (not necessarilyinjective) drawings or a rotation system.uvuvFigure 2.1. Two combinatorially equivalent but non-isotopic geodesictoroidal triangulations with parallel edges and loops. Opposite edges ofthe square are identified.two embeddings satisfy certain topological properties thatcharacterize isotopy [57–59].We explicitly consider embeddings of graphs withparallel edges and loops. In every geodesic toroidalembedding, every loop is non-contractible (since otherwiseit would be a single point), and no two parallel edgesare homotopic (since otherwise they would coincide). Inthis paper, we consider only geodesic embeddings; weoccasionally omit the word “geodesic” when it is clear fromcontext.The universal cover eΓ of a geodesic toroidal embedding Γ is the unique infinite straight-line plane graph whoseprojection to T is Γ ; that is, the projection of any vertex,edge, or face of eΓ is a vertex, edge, or face of Γ , respectively.A lift of any vertex u in Γ is any vertex in the preimageπ 1 (u) V (eΓ ). Similarly, each edge of Γ lifts to an infinitelattice of parallel line segments in R2 , and each face liftsto an infinite lattice of congruent e 2.2. Universal covers of the geodesic embeddings from Figure 2.1,with the link of one vertex emphasized in each.e in the universal cover eThe link of a vertex uΓ is thesimple polygon formed by the boundary of the union of thee; the vertices of the link are the(closed) faces incident to ue. We emphasize that when projecting a linkneighbors of udown to the flat torus, the vertices and edges of the linkneed not remain distinct; see Figure 2.1 for an example.For a vertex u in Γ , we informally write “link of u” to refere of u. Because the links ofto the link of an arbitrary lift uCopyright 2021 by SIAMUnauthorized reproduction of this article is prohibited

counting downward crossings). Crossing vectors are antisymmetric: x(rev(d)) x(d) for every dart d. SeeFigure 2.3. [–1,0]u[0,1]1,1] [–[0,0] v [–1,0]u[0,0] 1] [1,v1] [0,–any two lifts are congruent, any property proven about onelift applies to all of the others.Geometric properties of geodesics, polygons, andembeddings on the flat torus are defined by projectionfrom the universal cover. For example, the angle betweentwo edges (or geodesics) e and e0 at a common vertex u ise.equal to the angle between lifts ee and ee0 at a common lift uSimilarly, the cyclic order of edges around a vertex u of Γis the cyclic order of the corresponding edges around ane. In particular, if u is incident to a loop, thatarbitrary lift ueloop appears twice in cyclic order around u, and each lift uof u is incident to two different lifts of that loop. Finally,angles in the link of a vertex in Γ are projections of anglese.in the link of an arbitrary lift uA toroidal embedding Γ is a triangulation if everyface of Γ is bounded by three edges, or equivalently, if itsΓ is a planar triangulation. In particular, weuniversal cover edo not insist that triangulations are simplicial complexes.Every geodesic toroidal embedding Γ is essentially simple,meaning its universal cover eΓ is a planar embeddingof a simple (albeit infinite) graph. A geodesic toroidaldrawing Γ is essentially 3-connected if its universal cover eΓis 3-connected [45, 67–70]; every geodesic triangulation isessentially 3-connected.Figure 2.3. The geodesic embeddings from Figure 2.1, showing thecrossing vectors of all four darts from u to v .Crossing vectors and their generalizations have beenused in several previous algorithms for surface graphs[23–25, 37, 39, 40] and simplicial complexes [19, 34, 35] toencode the homology classes of cycles. Crossing vectors arealso equivalent to the translation vectors traditionally usedto model periodic (or “dynamic”) graphs [27, 31,48–50, 52,56, 73, 74, 85] and more recently used to model periodicbar-and-joint frameworks [16, 17, 33, 53, 64, 72, 77, 78].In principle, our morphing algorithm can be modifiedto update the coordinates of any vertex v and the crossing2.3 Coordinates and Crossing Vectors. To represent an vectors of darts incident to v whenever v crosses thearbitrary straight-line embedding of a graph in the plane, boundary of the unit square, with only a small penaltyit suffices to record the coordinates of each vertex; each in the running time. But in fact, this maintenance is notedge in the embedding is the unique line segment between necessary; it suffices to modify only the vertex coordinates,its endpoints. However, vertex coordinates alone are not keeping all crossing vectors fixed throughout the entiresufficient to specify a toroidal embedding; intuitively, we morph, even when vertices cross the boundary of the unitmust also specify how the edges of the graph wrap around square. We describe how to interpret toroidal embeddingswith these more relaxed coordinates in Appendix A.the surface.Formally, we regard each edge of the graph G as apair of opposing half-edges or darts, each directed fromone endpoint, called the tail, toward the other endpoint,called the head. We write rev(d) to denote the reversal ofany dart d; thus, for example, head(rev(d)) tail(d) andrev(rev(d)) d for every dart d.We can represent any geodesic embedding of anygraph G onto the torus by associating a coordinate vectorp(v) [0, 1)2 with every vertex v of G and a crossingvector x(d) Z2 with every dart d of G. The coordinatesof a vertex specify its position in the unit square; toremove any ambiguity, we assign points on the boundaryof the unit square coordinates on the bottom and/or leftedges. The crossing vector of a dart records how that dartcrosses the boundaries of the unit square. Specifically, thefirst coordinate of x(d) is the number of times d crossesthe vertical boundary to the rightward (with negativenumbers counting leftward crossings), and the secondcoordinate of x(d) is the number of times d crossesthe horizontal boundary upward (with negative numbers2.4 Equilibrium Embeddings. We make frequent use ofthe following natural generalization of Tutte’s “spring embedding” theorem for 3-connected planar graphs [84], firstproved by Y. Colin de Verdière [28] and later independentlyreproved by several others [32, 46, 62]:THEOREM 2.1. Let Γ be any essentially 3-connected geodesictoroidal drawing, where each edge e has an associated weightλ(e) 0. Then Γ is isotopic to a geodesic embedding Γ in Tsuch that every face is convex and each vertex is the weightedcenter of mass of its neighbors; moreover, this equilibriumembedding is unique up to translation.The equilibrium embedding Γ can be computed bysolving a linear system for the vertex coordinates p (v),treating the crossing vectors x(d) and weights λ(d) asconstants [28, 38, 46, 79]. For each vertex v, the systemcontains the constraintX (?)λ(d) · p (head(d)) x(d) p (v) (0, 0),tail(d) vCopyright 2021 by SIAMUnauthorized reproduction of this article is prohibited

where λ(d) λ(rev(d)) is the weight of the edge containing dart d. This linear system has a two-dimensional setof solutions, which differ by translation [28, 46]; we canremove this ambiguity by fixing p (r) (0, 0) for some arbitrary root vertex r [79]. Some vertex coordinates p (v) inthe solution to this system may lie outside the unit square;as we explain in Appendix A, it is possible to move allcoordinates back into the unit square by appropriately adjusting the crossing vectors, but in fact no such adjustmentis necessary.perturbing a pseudomorph consisting of edge collapsesand their reversals.3Technical OverviewIn this section, we give a technical overview of our results:at a high level, first we develop an algorithm to computea pseudomorph between geodesic toroidal triangulations,and then we describe how to use this algorithm to computea morph between essentially 3-connected geodesic toroidalembeddings. Here we give only a brief overview of severalThe support of this linear system is the toroidal necessary tools; each of these components is developed inpgraph G, which has balanced separators of size O( n) [3]. detail in a later section of the paper.Thus, the linear system can be solved in O(nω/2 ) time usingthe generalized nested dissection technique of Lipton et3.1 List of Ingredients. We begin with some essentialal. [61], where ω 2.37286 is the matrix multiplicationsubroutines and structural results.exponent [4, 60].3.1.1 Direct collapses. Following Cairns’ approach [20]2.5 Morphs and Pseudomorphs. A morph between and its later derivatives [1, 2, 6, 7, 10], a direct collapsetwo isotopic geodesic toroidal drawings Γ0 and Γ1 is a consists of moving a vertex u along some edge to anothercontinuous family of geodesic drawings (Γ t ) t [0,1] from vertex v, at uniform speed, until u and v coincide, keepingΓ0 to Γ1 ; in other words, a morph is a geodesic isotopy all other vertices fixed. To simplify our presentation, webetween Γ0 and Γ1 . Any morph is completely determined require that the moving vertex u is not incident to a loop.by the continuous motions on the vertices; geodesic edges We informally call a vertex good if it is not incident to aupdate in the obvious way.loop and it can be directly collapsed to one of its neighborsA morph is linear if every vertex moves along a without introducing any edge crossings, and bad otherwise;geodesic from its initial position to its final position at see Section 4 for a simple geometric characterization ofa uniform speed, and a morph is parallel if all vertices good vertices.move along parallel geodesics, that is, along projections ofAs noted by Cairns [20], every vertex of degree atparallel line segments.3 In this paper, we construct morphs most 5 not incident to a loop is good; indeed, this fact,that consist of a sequence of O(n) parallel linear morphs. along with the fact that every planar graph has a vertexEvery morph of this type can be specified by a sequence of degree at most 5, forms the basis of Cairns’ approachof isotopic geodesic toroidal embeddings Γ0 , . . . , Γk and for and its derivatives for computing (pseudo)morphs betweeneach index i, a set of parallel geodesics connecting the straight-line planar drawings. We prove in Lemma 6.1 thatvertices of Γi to corresponding vertices of Γi 1 .in any geodesic toroidal triangulation, a vertex of degree atLike many previous planar morphing algorithms, our most 5 cannot be incident to a loop, so in fact all verticesmorphing algorithm first constructs a pseudomorph, which of degree at most 5 are good.is a continuous family of drawings in which edges remainOn the other hand, Euler’s formula implies that thegeodesics, vertices may become coincident, but edges never average degree of a toroidal graph is exactly 6, and therecross. The most basic ingredient in our pseudomorph are simple examples of degree-6 vertices that are bad. Moris an edge collapse, which moves the endpoints of one phing between torus graphs thus requires new techniquesedge together until they coincide.4 Collapsing an edge to handle the special case of 6-regular triangulations.also collapses the faces on either side of that edge tosingle edges; edge collapses also preserve essential 3- 3.1.2 6-regular triangulations. We then prove inconnectivity. Our final morph is obtained by carefully Lemma 6.2 that if a 6-regular toroidal triangulation con-tains a loop, then in fact every vertex is incident to a loop;wecall this special type of triangulation a zipper. BecauseAlamdari et al. [1] and their predecessors [7, 10] call these “unidirectional" morphs; however, this term suggests incorrectly that vertices all the loops in any non-trivial zipper are parallel, morphingcannot move in opposite directions. Our usage differs from other papers, between isotopic zippers Z and Z turns out be straight01which use “parallel morph” to describe a morph that keeps each edgeforward. If the zippers have only one vertex, they differ byparallel to its original embedding [12–15].a single translation. Otherwise, two parallel linear morphs4This procedure is often called edge contraction in planar graphmorphing literature; we use the term “collapse” to avoid any confusion suffice, first sliding the loops of Z0 to coincide with thewith the topological notion of contractible cycles.corresponding loops in Z1 , and then rotating the loops to3Copyright 2021 by SIAMUnauthorized reproduction of this article is prohibited

!Figure 3.1. Our pseudomorph consists of a direct collapse, a recursive pseudomorph, and a reversed spring collapse.move vertices and non-loop edges to their locations in Z1 .We describe and analyze zippers in detail in Section 6.We analyze 6-regular triangulations without loops indetail in Section 4; we regard this analysis as the maintechnical contribution of the paper. Averaging argumentsimply that in any 6-regular triangulation where every vertexis bad, in short a bad triangulation, every vertex link isone of two specific non-convex hexagons that we call catsand dogs, illustrated in Figure 4.4. Analysis of how catsand dogs can overlap implies that any bad triangulationmust contain a non-contractible cycle of vertices (each ofwhose link is a cat) that consistently turns in the samedirection at every vertex, and therefore has non-zeroturning angle, contradicting the fact that the total turningangle of every non-contractible cycle on the flat torus iszero [75]. We conclude that bad triangulations do not exist;every geodesic toroidal triangulation that is not a zippercontains at least one good vertex.A vertex that is good in Γ0 might still be bad in Γ , so instead of applying a direct collapse to Γ , we introduce anovel method for collapsing edges in an equilibrium embedding in Section 5. Intuitively, we continuously increasethe weight of an arbitrary edge e to infinity, while maintaining the equilibrium triangulation given by Theorem 2.1.This spring collapse moves the endpoints of e together,just like a direct collapse. By analyzing the solutions to theequilibrium linear system (?), we show in Section 5.1 thata spring collapse is a parallel pseudomorph, and in factcan be simulated by an equivalent parallel linear pseudomorph. Moreover, this parallel linear pseudomorph can becomputed by solving a single instance of system (?).3.2 Recursive Pseudomorph Between Triangulations.We are now ready to describe our recursive algorithm tocompute a pseudomorph between two isotopic geodesic triangulations Γ0 and Γ1 . We actually explain how to computea pseudomorph Ψ0 from Γ0 to an isotopic equilibrium trian3.1.3 Equilibria and spring collapses. Suppose we are gulation Γ . The same algorithm gives a pseudomorph Ψ1given two isotopic geodesic triangulations Γ0 and Γ1 that from Γ1 to Γ , and concatenating Ψ0 with the reversal of Ψ1are not zippers. Our analysis implies that Γ0 and Γ1 each yields the desired pseudomorph from Γ0 to Γ1 .contain at least one good vertex. However, it is possibleIf Γ0 is a zipper, we morph directly between Γ0 andthat no vertex is good in both Γ0 and Γ1 . More subtly, eventhe equilibrium zipper Γ using at most two parallel linearif some vertex u is good in both triangulations, that vertexmorphs. This is the base case of our recursive algorithm.may be collapsible along a unique edge e0 in Γ0 but alongIf Γ0 is not a zipper, then it contains a good vertex u.a different unique edge e1 in Γ1 .Bydefinition,u can be directly collapsed along some edge eThe second problem also occurs for straight-line planartoanothervertexv, without introducing edge crossings.embeddings. Cairns’ solution to this problem was toThisdirectcollapsegives us a parallel linear pseudomorphintroduce an intermediate triangulation Γ1/2 in which u can0fromΓtoΓ,ageodesictoroidal triangulation whose0be collapsed along both e0 and e1 . Recursively constructing00underlyinggraphGhasn 1 vertices. On the other hand,pseudomorphs from Γ0 to Γ1/2 and from Γ1/2 to Γ1 yields aperformingaspringcollapsein Γ by increasing the weightpseudomorph from Γ0 to Γ1 with exponentially many steps.ofthesameedgeeto leadsto a drawing where uSubsequent refinements of Cairns’ approach, ulation Γ 0in the work of Alamdari et al. [1] and later improvement0000by Kleist et al. [54], obtained a pseudomorph with only of G that is isotopic to Γ0 . Finally, because Γ0 and Γ are0polynomial complexity by finding clever ways to avoid this isotopic embeddings of the same graph G , we can computea pseudomorph from Γ00 to Γ 0 recursively.intermediate triangulation.Our algorithm does introduce one intermediate trianOur full

6-regular triangulations of the torus. We also make heavy use of a natural extension of Tutte’s spring embedding theorem to torus graphs. 1 Introduction Computing a morph between two given geometric objects is a fundamental problem, with applications to questions i

Related Documents:

Coast Mental HealtH DeveloPment of the morPh - taBle of contents taBle of Contents executive summary preface Developing the MoRpH Introduction The current project Description of the MORPH pilot testing the MoRpH Objectives 19 Method 19 Results 20 Findings of the pilot study summary and Recommendations appendices Appendix 1: The MORPH

Image Pre-processing Using OpenCV Library on MORPH-II Face Database B. Yip, R. Towner, T. Kling, C. Chen, and Y. Wang ABSTRACT.This paper outlines the steps taken toward pre-processing the 55,134 images of the MORPH-II non-commercial dataset. Following the introduction, section two

Headshot Morph 1000 is the world's most comprehensive facial morph system. Specially designed for photo-modelling and controlled modification of Headshot photo-generated models, they can be used to produce virtually scan-level results. Headshot morphs can also be used for general modelling, and in tandem with existing Character Creator morphs.

Math 6 NOTES Name _ Types of Graphs: Different Ways to Represent Data Line Graphs Line graphs are used to display continuous data. Line graphs can be useful in predicting future events when they show trends over time. Bar Graphs Bar graphs are used to display categories of data.

difierent characterizations of pushdown graphs also show the limited expres-siveness of this formalism for the deflnition of inflnite graphs. Preflx Recognizable Graphs. The equivalence of pushdown graphs to the graphs generated by preflx rewriting systems on words leads to a natural extension of pushdown graphs.

plays (tables, bar graphs, line graphs, or Venn diagrams). [6] S&P-2 The student demonstrates an ability to analyze data (comparing, explaining, interpret-ing, evaluating; drawing or justifying conclusions) by using information from a variety of dis-plays (tables, bar graphs, line graphs, circle graphs, or Venn diagrams). Materials:

to address outnumber the available graphs. This paper demonstrates how to create your own ad. vanced graphs by intelligently combining existing graphs. This presentation explains how you can create the following types of graphs by combining existing graphs: a line-based graph that shows a line for each

The Alex Rider series is a fast-paced and action-packed set of books, ideal for lovers of spies and action. Teen readers will adore this unforgettable and enthralling series. Tomasz Hawryszczuk, age 9 This series of books is a must read for anyone over the age of 9 who likes spy stories, gadgets and danger. Best books ever! The Alex Rider series is an amazing set of books based on a 14 year .