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, Intervals in Catalan lattices and realizers of triangulations, Journal of Combinatorial Theory, Series A, vol.116, issue.1, pp.55-75, 2009.
DOI : 10.1016/j.jcta.2008.05.005

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-three 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.
DOI : 10.1007/s00454-006-1292-5
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.124.9963

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, Succinct representations of planar maps, Theoretical Computer Science, pp.174-187, 2008.
DOI : 10.1016/j.tcs.2008.08.016
URL : https://hal.archives-ouvertes.fr/inria-00337821

G. Chapuy, Asymptotic Enumeration of Constellations and Related Families of Maps on Orientable Surfaces, Combinatorics, Probability and Computing, vol.18, issue.04, 2008.
DOI : 10.1016/S0304-3975(02)00007-5
URL : https://hal.archives-ouvertes.fr/hal-00713483

G. Chapuy, M. Marcus, and G. Schaeffer, A Bijection for Rooted Maps on Orientable Surfaces, SIAM Journal on Discrete Mathematics, vol.23, issue.3, 2007.
DOI : 10.1137/080720097
URL : https://hal.archives-ouvertes.fr/hal-00713482

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-mendez17-]-´-e, F. Deverdì-ere, and . Lazarus, Orientations bipolaires Optimal system of loops on an orientable surface, Discrete & Computational Geometry FOCS'02, pp.507-534, 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. Fusy22, ´. E. Fusy, D. Poulalhon, and G. Schaeffer, Combinatoire des cartes planaires et applications algorithmiques Ecole Polytechnique Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling, In ACM Transactions on Algorithms, vol.4, issue.2, p.2008, 2007.

Z. Gao, A pattern for the asymptotic number of rooted maps on surfaces, Journal of Combinatorial Theory, Series A, vol.64, issue.2, pp.246-264, 1993.
DOI : 10.1016/0097-3165(93)90097-R

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

T. Lewiner, H. Lopes, and G. Tavares, Optimal discrete Morse functions for 2-manifolds, Computational Geometry, vol.26, issue.3, pp.221-233, 2003.
DOI : 10.1016/S0925-7721(03)00014-2

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

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

C. Rourke and B. Sanderson, Introduction to piecewise-linear topology, 1972.
DOI : 10.1007/978-3-642-81735-9

G. Schaeffer, Conjugaison d'arbres et cartes combinatoires aléatoires, 1999.

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.

R. E. Tarjan, Depth-First Search and Linear Graph Algorithms, SIAM Journal on Computing, vol.1, issue.2, pp.146-160, 1972.
DOI : 10.1137/0201010

R. E. Tarjan, A note on finding the bridges of a graph, Information Processing Letters, vol.2, issue.6, pp.160-161, 1974.
DOI : 10.1016/0020-0190(74)90003-9

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