论文标题
绘图图作为跨度
Drawing Graphs as Spanners
论文作者
论文摘要
我们研究将图形嵌入平面中的问题作为良好的几何跨度。也就是说，对于图形$ g $，目标是在飞机上构建直线绘制$γ$的$γ$ $ g $，以便，对于任何两个顶点$ u $ $ u $ $ u $和$ g $ $ g $的$ g $，从$ u $到$ v $的任何路径的最小长度与$ u $和$ u $和$ v $之间的最小路径之间的比率很小。在所有$ g $的顶点上，最大比率是$γ$的跨度比。 首先，我们表明，确定图表是否承认具有跨度比1 $的直线图，覆盖率为$ 1 $ $ 1 $的合适的直线图和带有跨度比1 $ 1 $的平面直线图是NP-Complete，$ \ \ Mathbb r $ $ - $ - compoble-complete和线性可溶解的问题，如果没有两个绘制的范围，则没有两个绘图的奖励，却是两个绘制的奖励。 其次，我们表明，从跨越比率$ 1 $转移到跨度比$ 1+ε$可以使我们绘制每个图。也就是说，我们证明，对于每$ε> 0 $，每个（平面）图都承认一个适当的（分别平面）直线图，其跨度比小于$ 1+ε$。 第三，我们的跨度比小于$ 1+ε$的图纸具有较大的边缘长度比，即，最长边缘的长度与最短边缘的长度之间的比率为指数。我们表明这有时是不可避免的。更普遍地，我们将有界韧性确定为区分图形的标准，该标准允许在持续的跨度比和多项式边缘长度比的直线图中与需要在任何直线图中具有恒定跨度比的指数边缘长度比的图形。
We study the problem of embedding graphs in the plane as good geometric spanners. That is, for a graph $G$, the goal is to construct a straight-line drawing $Γ$ of $G$ in the plane such that, for any two vertices $u$ and $v$ of $G$, the ratio between the minimum length of any path from $u$ to $v$ and the Euclidean distance between $u$ and $v$ is small. The maximum such ratio, over all pairs of vertices of $G$, is the spanning ratio of $Γ$. First, we show that deciding whether a graph admits a straight-line drawing with spanning ratio $1$, a proper straight-line drawing with spanning ratio $1$, and a planar straight-line drawing with spanning ratio $1$ are NP-complete, $\exists \mathbb R$-complete, and linear-time solvable problems, respectively, where a drawing is proper if no two vertices overlap and no edge overlaps a vertex. Second, we show that moving from spanning ratio $1$ to spanning ratio $1+ε$ allows us to draw every graph. Namely, we prove that, for every $ε>0$, every (planar) graph admits a proper (resp. planar) straight-line drawing with spanning ratio smaller than $1+ε$. Third, our drawings with spanning ratio smaller than $1+ε$ have large edge-length ratio, that is, the ratio between the length of the longest edge and the length of the shortest edge is exponential. We show that this is sometimes unavoidable. More generally, we identify having bounded toughness as the criterion that distinguishes graphs that admit straight-line drawings with constant spanning ratio and polynomial edge-length ratio from graphs that require exponential edge-length ratio in any straight-line drawing with constant spanning ratio.
