论文标题
具有恒定边缘分辨率的图形的网格图
Grid Drawings of Graphs with Constant Edge-Vertex Resolution
论文作者
论文摘要
我们研究了计算图的算法问题，其中$（i）$每个顶点是一个带有固定半径$ρ$，$（ii）$的磁盘，每个边缘是一个直线段，连接了代表其最终端口的两个磁盘的中心，代表其最终的$（iii）$ no twisks Intersect and（IV）的距离，并将其与diss Inders n nofe discement and（IV）隔开。 \ emph {edge-vertex分辨率}，至少为$ρ$。我们称此类图纸\ emph {disk-link图纸}。 在本文中，我们关注恒定边缘vertex分辨率的情况，即$ρ= \ frac {1} {2} $（即单位直径的磁盘）。我们证明，在任何此类磁盘 - 链接图中，都需要二次区域，在线性区域中毫无用处地录入了直线图。在正面，我们提出了建设性的技术，这些技术可在几个（平面和非平面）图类别的磁盘 - 链接图的面积需求（包括有限的带宽，完整和平面图）中产生上限。特别是，完整和平面图的呈范围渐近地紧密。
We study the algorithmic problem of computing drawings of graphs in which $(i)$ each vertex is a disk with fixed radius $ρ$, $(ii)$ each edge is a straight-line segment connecting the centers of the two disks representing its end-vertices, $(iii)$ no two disks intersect, and $(iv)$ the distance between an edge segment and the center of a non-incident disk, called \emph{edge-vertex resolution}, is at least $ρ$. We call such drawings \emph{disk-link drawings}. In this paper we focus on the case of constant edge-vertex resolution, namely $ρ=\frac{1}{2}$ (i.e., disks of unit diameter). We prove that star graphs, which trivially admit straight-line drawings in linear area, require quadratic area in any such disk-link drawing. On the positive side, we present constructive techniques that yield improved upper bounds for the area requirements of disk-link drawings for several (planar and nonplanar) graph classes, including bounded bandwidth, complete, and planar graphs. In particular, the presented bounds for complete and planar graphs are asymptotically tight.
