Optimizing the Width of a Visibility Representation of Planar Graphs
Date Issued
2005
Date
2005
Author(s)
FAN, Jia-Hao
DOI
en-US
Abstract
In a visibility representation of a planar graph G, each node of G is represented by a horizontal segment and each edge of G is represented by a vertical segment, and incidence between nodes and edges translates to intersection of horizontal and vertical segments. The grid size is at most (2n - 4)*(n - 1) for a graph with n nodes. G must not contain self-loops or multiple edges. We find an algorithm to draw a general planar graph to its visibility representation with width 4n/3 in O(n). More specifically, for an n-node planar graph G, we can obtain its 6 visibility drawings from a 3-node triangle’s 6 visibility drawings by applying a sequence of operations, and the sum of the widths of the six visibility representation of an n-node planar graph is 8n + O(1). Clearly there is at least one visibility representation among the six with the width smaller than 4n / 3 + O(1)
Subjects
圖論及演算法
graph drawing and graph algorithm
visibility representation
VLSI design
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-94-R92921077-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):ae32481f8f04f1559e01a26669d0a7c2