English

19 Pages

Gain access to the library to view online

__
Learn more
__

Description

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.

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

Subjects

Informations

Published by | chaeh |

Reads | 7 |

Language | English |

Report a problem