Planar Graphs via Well Orderly Maps and Trees

Niveau: Supérieur
Planar Graphs, via Well-Orderly Maps and Trees Ni olas Boni hon 1 , Cyril Gavoille 1 , Ni olas Hanusse 1 , Dominique Poulalhon 2 , Gilles S haeer 3 1 Laboratoire Bordelais de Re her he en Informatique, Universite Bordeaux I, Fran e fboni hon, gavoille, hanusseglabri.fr 2 Laboratoire d'Informatique Algorithmique, Fondements et Appli ations (LIAFA) ase 7014, 2, pla e Jussieu, 75251 Paris Cedex 05, Fran e poulalhonliafa.jussieu.fr 3 Laboratoire d'Informatique de l' E ole Polyte hnique (LIX) E ole polyte hnique, 91128 Palaiseau Cedex, Fran e gilles.s haeerlix.polyte hnique.fr Abstra t The family of well-orderly maps is a family of planar maps with the property that every onne ted planar graph has at least one plane embedding whi h is a well-orderly map. We show that the number of well-orderly maps with n nodes is at most 2 n+O(log n) , where 4:91. A dire t onsequen e of this is a new upper bound on the number p(n) of unlabeled planar graphs with n nodes, log 2 p(n) 6 4:91n.

• onne ted


• planar graph


• orderly map


• no known


• planar graphs


• all interior


• well-orderly maps


• priori no unique