Planar Graphs, via Well-Orderly Maps and Trees |
| |
Authors: | Nicolas Bonichon Cyril Gavoille Nicolas Hanusse Dominique Poulalhon Gilles Schaeffer |
| |
Institution: | (1) Laboratoire Bordelais de Recherche en Informatique, Université Bordeaux I, France;(2) Laboratoire d'Informatique Algorithmique, Fondements et Applications (LIAFA) case 7014, 2, place Jussieu, 75251 Paris Cedex 05, France;(3) Laboratoire d'Informatique de l'école Polytechnique (LIX) école polytechnique, 91128 Palaiseau Cedex, France |
| |
Abstract: | The family of well-orderly maps is a family of planar maps with the property that every connected planar graph has at least
one plane embedding which is a well-orderly map. We show that the number of well-orderly maps with n nodes is at most 2αn+O(logn), where α≈4.91. A direct consequence of this is a new upper bound on the number p(n) of unlabeled planar graphs with n nodes, log2p(n)≤4.91n.
The result is then used to show that asymptotically almost all (labeled or unlabeled), (connected or not) planar graphs with
n nodes have between 1.85n and 2.44n edges.
Finally we obtain as an outcome of our combinatorial analysis an explicit linear-time encoding algorithm for unlabeled planar
graphs using, in the worst-case, a rate of 4.91 bits per node and of 2.82 bits per edge. |
| |
Keywords: | Planar graph Triangulation Realizer Well-orderly |
本文献已被 SpringerLink 等数据库收录! |
|