Reconfiguring Triangulations with Edge Flips and Point Moves

Aloupis, Greg and Bose, Prosenjit and Morin, Pat (2004) Reconfiguring Triangulations with Edge Flips and Point Moves. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 1-11 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_1).

Full text not available from this repository.

Abstract

We examine reconfigurations between triangulations and near-triangulations of point sets, and give new bounds on the number of point moves and edge flips sufficient for any reconfiguration. We show that with O(n log n) edge flips and point moves, we can transform any geometric near-triangulation on n points to any other geometric near-triangulation on n possibly different points. This improves the previously known bound of O(n^2) edge flips and point moves. Research supported in part by the Natural Science and Engineering Council of Canada.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_1
Classifications:Z Theory > Z.250 Geometry
ID Code:556

Repository Staff Only: item control page

References

Abellanas, M., Bose, P., Garcia, A., Hurtado, F., Ramos, P., Rivera-Campo, E., Tejel, J.: On local transformations in plane geometric graphs embedded on small grids. In Proceedings of the International Workshop on Computational Geometry and Applications (CGA) 2 (2004) 22-31

Bose, P., Czyzowicz,J., Gao, Z., Morin, P., Wood, D.: Parallel diagonal flips in plane triangulations. Tech. Rep. TR-2003-05, School of Computer Science, Carleton University, Ottawa, Canada (2003)

Brunet, R., Nakamoto, A., Negami, S.: Diagonal flips of triangulations on closed surfaces preserving specified properties. J. Combin. Theory Ser. B 68 (2) (1996) 295-309

Cortés, C., Grima, C., Marquez, A., Nakamoto, A.: Diagonal flips in outer-triangulations on closed surfaces. Discrete Math. 254 (1-3) (2002) 63-74

Cortés, C., Nakamoto, A.:Diagonal flips in outer-torus triangulations. Discrete Math. 216 (1-3) (2000) 71-83

Galtier, J., Hurtado, F., Noy, M., Pérennes, S., Urrutia, J.: Simultaneous edge flipping in triangulations. Internat, J. Comput. Geom. Appl. 13(2) (2003) 113-133

Gao, Z., Urrutia, J., Wang, J.: Diagonal flips in labelled planar triangulations. Graphs Combin. 17(4) (2001) 647-657

Hurtado F., Noy, M.: Graph of triangulations of a convex polygon and tree of triangulations. Comput. Geom. 13(3) (1999) 179-188

Hurtado, F., Noy, M., Urrutia, J. Flipping edges in triangulations. Discrete Comput. Geom. 22(3) (1999) 333-346

Komuro, H.: The diagonal flips of triangulations on the sphere. Yokohama Math. J. 44(2) (1997) 115-122

Komuro, H., Nakamoto, A., Negami, S.: Diagonal flips in riangulations on closed surfaces with minimum degree at least 4. J. Combin. Theory Ser. B 76(1) (1999) 68-92

Lawson, C.: Software for c1 surface interpolation. In J. Rice, ed., Mathematical Software III, pp. 161-194, Academic Press, New York (1977)

Meisters, G.: Polygons have ears. American Mathematical Monthly 82 (1975) 648-651

Nakamoto, A., Negami, S.: Diagonal flips in graphs on closed surfaces with specified face size distributions. Yokohama Math. J. 49(2) (2002) 171-180

Negami, S.: Diagonal flips in triangulations of surfaces. Discrete Math. 135(1-3) (1994) 225-232

Negami, S.: Diagonal flips in triangulations on closed surfaces, estimating upper bounds. Yokohama Math. J. 45(2) (1998) 113-124

Negami, S.: Diagonal flips of triangulations on surfaces, a survey. Yokohama Math. J. 47 (1999) 1-40

Negami, S., Nakamoto, A.: Diagonal transformations of graphs on closed surfaces. Sci. Rep. Yokohama Nat. Univ. Sect. I Math. Phys. Chem. 40 (1993) 71-97

Wagner, K.: Bemerkung zum Vierfarbenproblem. Jber. Deutsch. Math.- Verein. 46 (1936) 26-32

Watanabe, T., Negami, S.: Diagonal flips in pseudo-triangulations on closed surfaces without loops. Yokohama Math. J. 47 (1999) 213-223