J. Barbay, L. Castelli-aleardi, M. He, and J. I. Munro, Succinct representation of labeled graphs, ISAAC, pp.316-328, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00712915

O. Bernardi and N. Bonichon, Catalans intervals and realizers of triangulations, Proc. FPSAC07, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00307858

N. Bonichon, Aspects algorithmiques et combinatoires des réaliseurs des graphes plans maximaux, 2002.

N. Bonichon, C. Gavoille, and N. Hanusse, An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation, STACS, pp.499-510, 2003.
DOI : 10.1007/3-540-36494-3_44
URL : https://hal.archives-ouvertes.fr/hal-00307599

N. Bonichon, C. Gavoille, N. Hanusse, D. Poulalhon, and G. Schaeffer, Planar Graphs, via Well-Orderly Maps and Trees, Graphs and Combinatorics, vol.22, issue.2, pp.185-202, 2006.
DOI : 10.1007/s00373-006-0647-2
URL : https://hal.archives-ouvertes.fr/hal-00307603

N. Bonichon, C. Gavoille, and A. Labourel, Edge Partition of Toroidal Graphs into Forests in Linear Time, ICGT, pp.421-425, 2005.
DOI : 10.1016/j.endm.2005.06.065
URL : https://hal.archives-ouvertes.fr/hal-00307600

E. Brehm, 3-orientations and schnyder-trhree tree decompositions. Master's thesis, 2000.

S. Cabello and B. Mohar, Finding shortest non-separating and noncontractible cycles for topologically embedded graphs, Discrete & Comp. Geometry, pp.213-235, 2007.

L. Castelli-aleardi, O. Devillers, and G. Schaeffer, Succinct representation of triangulations with a boundary, WADS, pp.134-145, 2005.
URL : https://hal.archives-ouvertes.fr/inria-00090707

L. Castelli-aleardi, O. Devillers, and G. Schaeffer, Optimal succinct representations of planar maps, SoCG, pp.309-318, 2006.
URL : https://hal.archives-ouvertes.fr/inria-00098669

Y. Chiang, C. Lin, and H. Lu, Orderly spanning trees with applications to graph encoding and graph drawing, SODA, pp.506-515, 2001.

H. De-fraysseix and P. O. De-mendez, On topological aspects of orientations, Discrete Mathematics, vol.229, issue.1-3, pp.57-72, 2001.
DOI : 10.1016/S0012-365X(00)00201-6
URL : https://hal.archives-ouvertes.fr/hal-00005628

P. O. De-mendez, Orientations bipolaires [15] ´ E. C. deVerdì ere and F. Lazarus. Optimal system of loops on an orientable surface, FOCS, pp.627-636, 1994.

J. Erickson and S. Har-peled, Optimally Cutting a Surface into a Disk, Discrete and Computational Geometry, vol.31, issue.1, pp.37-59, 2004.
DOI : 10.1007/s00454-003-2948-z

S. Felsner, Convex drawings of planar graphs and the order dimension of 3-polytopes. Order, pp.19-37, 2001.

S. Felsner, Lattice structures from planar graphs, Electronic Journal of Combinatorics, vol.11, issue.15, p.24, 2004.

E. Fusy, Combinatoire des cartes planaires et applications algorithmiques, 2007.

E. Fusy, D. Poulalhon, and G. Schaeffer, Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling, SODA, pp.690-699, 2005.
DOI : 10.1145/1361192.1361196
URL : https://hal.archives-ouvertes.fr/hal-00330580

X. He, M. Kao, and H. Lu, Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings, SIAM Journal on Discrete Mathematics, vol.12, issue.3, pp.317-325, 1999.
DOI : 10.1137/S0895480197325031

G. Kant, Drawing planar graphs using the canonical ordering, Algorithmica, vol.46, issue.1, pp.4-32, 1996.
DOI : 10.1007/BF02086606

K. Keeler and J. Westbrook, Short encodings of planar graphs and maps, Discrete Applied Mathematics, vol.58, issue.3, pp.239-252, 1995.
DOI : 10.1016/0166-218X(93)E0150-W

M. Kutz, Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time, Proceedings of the twenty-second annual symposium on Computational geometry , SCG '06, pp.430-438, 2006.
DOI : 10.1145/1137856.1137919

F. Lazarus, M. Pocchiola, G. Vegter, and A. Verroust, Computing a canonical polygonal schema of an orientable triangulated surface, Proceedings of the seventeenth annual symposium on Computational geometry , SCG '01, pp.80-89, 2001.
DOI : 10.1145/378583.378630
URL : https://hal.archives-ouvertes.fr/hal-00804691

T. Lewiner, H. Lopes, J. Rossignac, and A. W. Vieira, Efficient Edgebreaker for surfaces of arbitrary topology, Proceedings. 17th Brazilian Symposium on Computer Graphics and Image Processing, pp.218-225, 2004.
DOI : 10.1109/SIBGRA.2004.1352964

H. Lopes, J. Rossignac, A. Safonova, A. Szymczak, and G. Tavares, Edgebreaker: a simple implementation for surfaces with handles, Computers & Graphics, vol.27, issue.4, pp.553-567, 2003.
DOI : 10.1016/S0097-8493(03)00102-X

B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins, 2001.

D. Poulalhon and G. Schaeffer, Optimal Coding and Sampling of Triangulations, Algorithmica, vol.46, issue.3-4, pp.505-527, 2006.
DOI : 10.1007/s00453-006-0114-8
URL : https://hal.archives-ouvertes.fr/hal-00159287

J. Rossignac, Edgebreaker: connectivity compression for triangle meshes, IEEE Transactions on Visualization and Computer Graphics, vol.5, issue.1, pp.47-61, 1999.
DOI : 10.1109/2945.764870

W. Schnyder, Planar graphs and poset dimension. Order, pp.323-343, 1989.
DOI : 10.1007/bf00353652

W. Schnyder, Embedding planar graphs on the grid, SODA, pp.138-148, 1990.

G. Turan, On the succinct representation of graphs, Discrete Applied Mathematics, vol.8, issue.3, pp.289-294, 1984.
DOI : 10.1016/0166-218X(84)90126-4

W. Tutte, A census of planar maps, Journal canadien de math??matiques, vol.15, issue.0, pp.249-271, 1963.
DOI : 10.4153/CJM-1963-029-x

G. Vegter and C. Yap, Computational complexity of combinatorial surfaces, Proceedings of the sixth annual symposium on Computational geometry , SCG '90, pp.102-111, 1990.
DOI : 10.1145/98524.98546