An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation
An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation
复制标题
使用三角测量的平面图的信息论上限
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Nicolas Hanusse
中科院分区：
文献类型：
--
作者：
Nicolas Bonichon;C. Gavoille;Nicolas Hanusse
我们提出了一个新的线性时间算法来表示平面图。基于图的特定三角剖分，我们的编码平均每个节点占用5.03位，如果图是最大的，则每个节点占用3.37位。我们从这个表示，n个节点的未标记平面图的数量是最多2？n+O（log n），其中？? 5.007.目前的下限是2sn+？(log n）对于s？4.71.我们还证明了几乎所有的未标号和几乎所有的标号n-节点平面图至少有1.70 n条边，最多有2.54 n条边。
We propose a new linear time algorithm to represent a planar graph. Based on a specific triangulation of the graph, our coding takes on average 5.03 bits per node, and 3.37 bits per node if the graph is maximal. We derive from this representation that the number of unlabeled planar graphs with n nodes is at most 2?n+O(log n), where ? ? 5.007. The current lower bound is 2sn+?(log n) for s ? 4.71. We also show that almost all unlabeled and almost all labeled n-node planar graphs have at least 1.70n edges and at most 2.54n edges.