Computer Science ETDs

Publication Date

5-1-2016

Abstract

The one-sided bipartite graph drawing problem has been extensively studied in the graph drawing literature, with numerous papers appearing over the years showing novel algorithms and heuristics for minimizing associated edge crossings. Although stochastic methods have been highly successful when applied to bipartite graph drawing, a large, comprehensive study to compare said methods has not been carried out for one-sided crossing minimization on traditional, unweighted graphs. Even more so, the variant problems of weighted and bottleneck bipartite crossing minimization have seldom been studied, with only one published algorithm, 3-WOLF (designed for one-sided weighted crossing minimization), and one published heuristic, MEC (designed for multi-layer bottleneck crossing minimization) appearing in the literature. To date there has been no published work for handling one-sided bottleneck crossing minimization. This thesis helps to close some of these gaps in the graph drawing literature. A comparative study of stochastic methods for one-sided bipartite graph drawing is carried out on both unweighted and weighted bipartite graphs. Novel variants of two previously published genetic algorithms, a one-sided version of a hybrid simulated annealing algorithm, a stochastic hill climbing procedure, and a top performing approximation algorithm, 3-WOLF, are compared against each other and the standard benchmark barycenter heuristic on weighted and unweighted bipartite graphs. Both unweighted and weighted versions of barycenter are considered. In addition, a novel bottleneck crossings based stochastic hill climbing procedure is compared against a one-sided variant of the MEC heuristic for one-sided bottleneck crossing minimization. The algorithms in this latter set of tests are conducted with and without barycenter preprocessing. Stochastic hill climbing was found to obtain the best results for all of the bipartite graph drawing problems, significantly outperforming the other methods in the weighted and bottleneck crossing contexts. The results of bottleneck crossing based stochastic hill climbing were slightly improved with barycenter preprocessing. These experimental findings are particularly notable in the weighted and bottleneck crossing cases, since 3-WOLF is one of the best methods for weighted one-sided crossing minimization and MEC the best for multi-layer bottleneck crossing minimization. In regards to barycenter, although it didnt perform well for weighted crossing minimization, it was interesting to find that its traditional unweighted variant worked better for weighted crossing minimization than its edge-weighted version.

Language

English

Keywords

bipartite, graph, drawing, crossing, minimization, stochastic, weighted, bottleneck

Document Type

Thesis

Degree Name

Computer Science

Level of Degree

Masters

Department Name

Department of Computer Science

First Committee Member (Chair)

Kelley, Patrick

Second Committee Member

Loring, Terry

Third Committee Member

Hayes, Thomas

Download

Share

COinS