Hypergraph Drawing with Backbones
Date Issued
2015
Date
2015
Author(s)
Tsai, Hsuan-Yin
Abstract
The thesis mainly discusses various optimization problems with respect to three aesthetic criteria in hypergraph drawings under the condition that each hyperedge has one backbone. The aesthetic criteria include minimizing the number of crossings, the total hyperedge length, and maximizing the number of hyperedges under the condition that a hypergraph has no overlapping hyperedge. In the aspect of crossings minimization, if there is an order among the hyperedges, we can use a dynamic programming algorithm to solve it. In the aspect of total length minimization, we transform the problem into the bipartite matching problem to solve it. In the aspect of maximizing the number of hyperedges, a greedy algorithm is proposed. Also, the thesis considers three different types of backbones: with horizontal backbones only, with both horizontal and vertical backbones, and allowing horizontal, vertical and octilinear horizontal backbones.
Subjects
graph drawing
hypergraph
crossing minimization
length minimization
backbone
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-104-R02921040-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):dc3c8f540eaae98d9dde82135c95f8fc