Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Planar Graphs, via Well-Orderly Maps and Trees
verfasst von : Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon, Gilles Schaeffer
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
(
log
n
)
, 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, log
2
p
(
n
) ≤ 4.91
n
.
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.85
n
and 2.44
n
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.