论文标题
平面图（及以后）的邻接标签
Adjacency Labelling for Planar Graphs (and Beyond)
论文作者
论文摘要
我们表明，存在针对平面图的邻接标记方案，其中为$ n $ -vertex平面图$ g $的每个顶点分配了$（1+o（1））\ log_2 n $ - bit-bitel和两个顶点$ u $ and $ u $和$ v $的标签，足以确定$ uv $ uv $是$ g $ expe of $ g $。这是最佳的较低阶段，并且是第一个这样的渐近最佳结果。对此结果的一种替代性但同等的解释是，对于每$ n $，都存在一个图$ u_n $，其中$ n^{1+o（1）} $ vertices，因此每个$ n $ n $ vertex planar graph都是$ u_n $的诱导子图。这些结果概括为有界属图，无顶点的图形，次要封闭族的有界图和$ k $ - 平面图。
We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an $n$-vertex planar graph $G$ is assigned a $(1+o(1))\log_2 n$-bit label and the labels of two vertices $u$ and $v$ are sufficient to determine if $uv$ is an edge of $G$. This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every $n$, there exists a graph $U_n$ with $n^{1+o(1)}$ vertices such that every $n$-vertex planar graph is an induced subgraph of $U_n$. These results generalize to bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and $k$-planar graphs.
