D. W. Barnette, Generating the triangulations of the projective plane, Journal of Combinatorial Theory, Series B, vol.33, issue.3, pp.222-230, 1982.
DOI : 10.1016/0095-8956(82)90041-7

O. Devillers, THE DELAUNAY HIERARCHY, International Journal of Foundations of Computer Science, vol.13, issue.02, pp.163-180, 2002.
DOI : 10.1142/S0129054102001035
URL : https://hal.archives-ouvertes.fr/inria-00166711

O. Devillers and A. Mukhopadhyay, Finding an ordinary conic and an ordinary hyperplane, Nordic J. Comput, vol.6, pp.422-428, 1999.
URL : https://hal.archives-ouvertes.fr/inria-00168174

O. Devillers, S. Pion, and M. Teillaud, WALKING IN A TRIANGULATION, International Journal of Foundations of Computer Science, vol.13, issue.02, pp.181-199, 2002.
DOI : 10.1142/S0129054102001047
URL : https://hal.archives-ouvertes.fr/inria-00344519

A. K. Dewdney, Wagner's theorem for Torus graphs, Discrete Mathematics, vol.4, issue.2, pp.139-149, 1973.
DOI : 10.1016/0012-365X(73)90076-9
URL : http://doi.org/10.1016/0012-365x(73)90076-9

H. Edelsbrunner and T. S. Tan, A Quadratic Time Algorithm for the Minmax Length Triangulation, SIAM Journal on Computing, vol.22, issue.3, pp.527-551, 1993.
DOI : 10.1137/0222036

D. Eppstein, Happy endings for flip graphs, Proceedings of the twenty-third annual symposium on Computational geometry , SCG '07, pp.92-101, 2007.
DOI : 10.1145/1247069.1247084
URL : http://arxiv.org/abs/cs/0610092

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP- Completeness, 1979.

M. Henle, A Combinatorial Introduction to Topology, 1979.

L. Kelly and W. Moser, On the number of ordinary lines determined by $n$ points, Journal canadien de math??matiques, vol.10, issue.0, pp.210-219, 1958.
DOI : 10.4153/CJM-1958-024-6

R. Mori and A. Nakamoto, Diagonal flips in Hamiltonian triangulations on the projective plane, Discrete Mathematics, vol.303, issue.1-3, pp.142-153, 2005.
DOI : 10.1016/j.disc.2004.12.021

A. Mukhopadhyay, A. Agrawal, and R. M. Hosabettu, On the ordinary line problem in computational geometry, Nordic J. Comput, vol.4, pp.330-341, 1997.

W. Mulzer and G. Rote, Minimum-weight triangulation is NP-hard, Journal of the ACM, vol.55, issue.2, 2007.
DOI : 10.1145/1346330.1346336
URL : http://arxiv.org/abs/cs/0601002

S. Negami, Diagonal flips in triangulations of surfaces, Discrete Mathematics, vol.135, issue.1-3, pp.225-232, 1994.
DOI : 10.1016/0012-365X(93)E0101-9

S. Negami, Diagonal flips in triangulations on closed surfaces, a survey, Yokohama Math. J, vol.47, pp.1-40, 1999.

S. Negami and S. Watanabe, Diagonal transformations of triangulations on surfaces, Tsubuka J. Math, vol.14, pp.155-166, 1990.

J. Stolfi, Oriented projective geometry, Proceedings of the third annual symposium on Computational geometry , SCG '87, 1991.
DOI : 10.1145/41958.41966

K. Wagner, Bemerkungen zum Vierfarbenproblem, Jahresbericht der Deutschen Mathematiker- Vereinigung, vol.46, pp.26-32, 1936.

J. Afra and . Zomorodian, Topology for Computing, 2005.

. Unité-de-recherche-inria-sophia and . Antipolis, route des Lucioles -BP 93 -06902 Sophia Antipolis Cedex (France) Unité de recherche INRIA Futurs : Parc Club Orsay Université -ZAC des Vignes 4, 2004.

I. Unité-de-recherche and . Lorraine, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602 Villers-lès-Nancy Cedex (France) Unité de recherche INRIA Rennes : IRISA, Campus universitaire de Beaulieu -35042 Rennes Cedex (France) Unité de recherche INRIA Rhône-Alpes : 655, avenue de l'Europe -38334 Montbonnot Saint-Ismier (France) Unité de recherche INRIA Rocquencourt, Domaine de Voluceau -Rocquencourt -BP 105 -78153 Le Chesnay Cedex