Bounded Degree Book Embeddings and Three-Dimensional Orthogonal Graph Drawing
Bounded Degree Book Embeddings and Three-Dimensional Orthogonal Graph Drawing
复制标题
有界度书嵌入和三维正交图绘制
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
D. Wood
中科院分区：
文献类型：
--
作者：
D. Wood
图形的图书嵌入包括沿三维空间中的直线对顶点进行线性排序（书脊），以及以书脊为边界（页面）将边缘分配给半平面，以便分配给同一页的边缘可以在该页上绘制而不会交叉。给定图G = (V，E)，设f: V→n是1≤f(υ)≤deg（υ）的函数。我们提出了一种Las Vegas算法，该算法产生具有(O(sqrt {|E| cdot max _upsilon leftlceil {deg （upsilon)/f(upsilon)} ight
ceil}）页的G的图书嵌入，使得与顶点v相关的最多f(v)条边位于单个页面上。该算法对现有的图书嵌入结果进行了推广。我们应用该算法生成了每条边有一个弯、体积为O（∣V∣3/2∣E∣）的三维正交图，以及每条边有两个弯、体积相同的单排图。在生成的图纸中，每条边都完全包含在某个z平面中；这样的图纸没有所谓的横切，特别适用于多层VLSI的应用。使用不同的方法，我们以O（∣V∣E∣）体积实现了每条边的两个弯曲，但具有交叉切割。这些结果建立了三维正交图形体积的改进边界。
A book embedding of a graph consists of a linear ordering of the vertices along a line in 3-space (the spine), and an assignment of edges to half-planes with the spine as boundary (the pages), so that edges assigned to the same page can be drawn on that page without crossings. Given a graph G = (V,E), let f : V → ℕ be a function such that 1 ≤ f(υ) ≤ deg(υ). We present a Las Vegas algorithm which produces a book embedding of G with ( O(sqrt {|E| cdot max _upsilon leftlceil {deg (upsilon )/f(upsilon )}
ight
ceil } ) ) pages, such that at most f(v) edges incident to a vertex v are on a single page. This algorithm generalises existing results for book embeddings. We apply this algorithm to produce 3-D orthogonal drawings with one bend per edge and O(∣V ∣3/2∣E∣) volume, and single-row drawings with two bends per edge and the same volume. In the produced drawings each edge is entirely contained in some Z-plane; such drawings are without so-called cross-cuts, and are particularly appropriate for applications in multilayer VLSI. Using a different approach, we achieve two bends per edge with O(∣V ∣∣E∣) volume but with cross-cuts. These results establish improved bounds for the volume of 3-D orthogonal graph drawings.