Optimizing Various Aesthetic Criteria in Two-Dimensional Graph Drawing
Date Issued
2009
Date
2009
Author(s)
Lin, Chun-Cheng
Abstract
As graphs are known to be one of the most important abstract models in various scientific and engineering areas, graph drawing has naturally emerged as a fast growing research topic in computer science. Conventional graph drawing algorithms are designed to confirm to one or more aesthetic criteria of nice drawings. In this research, we investigate to optimize various aesthetic criteria in two-dimensional drawings of three graph classes, form the simplest to the most complicated.irst, we study balloon drawings of rooted trees, in which each subtree is enclosed in a circle. In balloon drawings, the sizes of the drawing angles significantly affect the drawing articulation. Therefore, in this research, we investigate the problem of optimizing various measures of angles, i.e., angular resolution, aspect ratio of angles, as well as standard deviation of angles, under different setting of balloon drawings. In addition, we provide some applications on balloon drawings.econd, we study two- and three- layered network drawings (in which nodes are drawn on two and three vertical lines, respectively) with application to many-to-one boundary labeling, in which more than one point site allows to be connected to a common label on the four sides of an enclosing rectangular map by a leader (which may be a rectilinear or straight line segment). In this research, we apply two- and three- layered network drawings to solving the problem of minimizing the number of crossings among leaders under certain one-side and two-side labeling schemes. Furthermore, we design the labeling without any crossing by substituting hyperleaders for leaders and applying dummy labels.hird, we study the visibility representations of plane graphs, in which each node is drawn as a horizontal line segment such that the line segments associated with any two adjacent nodes are vertically visible to each other. In this research, we give an O(n)-time algorithm to find a visibility representation of an n-node plane graph no wider than $ /lfloor 4n/3 /rfloor - 2 $, which achieves optimality in the upper bound of width because the bound differs from the previously known lower bound only by one unit.
Subjects
graph drawing
graph algorithm
balloon drawing
boundary labeling
visibility representation
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-F89921122-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):13a437fc146022ff6cb11453efe8eeb1