论文标题
贪婪可绘制的树木的完整组合表征
Complete combinatorial characterization of greedy-drawable trees
论文作者
论文摘要
图形的（欧几里得）贪婪图纸是一张图纸，对于任何两个顶点$ s，t $（$ s \ neq t $），邻居顶点$ s $比euclidean距离的$ s $更接近$ t $。贪婪的图纸在网络中的消息路由的背景下很重要，并且已经积极研究了贪婪图纸的图形类。 Nöllenburgand Prutkin（离散计算机Geom。，58（3），第543-579页，2017年）根据包含非线性方程式的不平等系统的贪婪可挖掘树的表征。使用表征，他们为贪婪的可绘制树提供了线性时间识别算法，该算法的最大程度$ \ leq 4 $。但是，最高度5的贪婪可绘制树的组合表征被打开。在本文中，我们给出了最高度$ 5 $的贪婪可绘制树的组合表征，这导致了贪婪的可绘制树的完整组合表征。此外，我们给出了贪婪的可绘制伪树的特征。
A (Euclidean) greedy drawing of a graph is a drawing in which, for any two vertices $s,t$ ($s \neq t$), there is a neighbor vertex of $s$ that is closer to $t$ than to $s$ in the Euclidean distance. Greedy drawings are important in the context of message routing in networks, and graph classes that admit greedy drawings have been actively studied. Nöllenburg and Prutkin (Discrete Comput. Geom., 58(3), pp.543-579, 2017) gave a characterization of greedy-drawable trees in terms of an inequality system that contains a non-linear equation. Using the characterization, they gave a linear-time recognition algorithm for greedy-drawable trees of maximum degree $\leq 4$. However, a combinatorial characterization of greedy-drawable trees of maximum degree 5 was left open. In this paper, we give a combinatorial characterization of greedy-drawable trees of maximum degree $5$, which leads to a complete combinatorial characterization of greedy-drawable trees. Furthermore, we give a characterization of greedy-drawable pseudo-trees.
