Abstract
dc:descriptionRectilinear crossing number of a graph is the number of crossing edges in a drawing with all straight line edges. The problem of drawing an n-vertex complete graph such that its rectilinear crossing number is minimum is known to be an NP-Hard problem. In this thesis, we present a heuristic that attempts to achieve the theoretical lower bound value of the rectilinear crossing number of a n+1 vertex complete graph from that of n vertices. Our algorithm accepts an optimal or near-optimal rectilinear drawing of Kn graph as input and tries to place a new node such that the crossing number is minimized. Based on prior optimal drawings of Kn, we make an empirical observation that the optimal drawings are triangular in shape. The proposed heuristic has three steps: (1) Given the optimal or near-optimal drawing of Kn, the outer triangle is determined; (2) A set of candidate positions for the (n+1)th node is determined by ensuring none of them are collinear with two or more nodes in the graph; and (3) the best drawing with least rectilinear crossing number is chosen based on the drawings corresponding to the candidate position. A loose bound on the worst-case time complexity of the proposed algorithm is O(n7). The heuristic is not guaranteed to yield optimal solution as the search space is constrained by the input graph. In our experimental results, we obtained optimal results for complete graphs of up to n=27.
Degree
thesis:*- Name thesis:degree_name
- MS in Computer Science (M.S.C.S.)
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Computer Science and Engineering
- Grantor
- University of South Florida
- Year dc:date
- 2017
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Revoori, Soundarya
- Contributors dc:contributor
-
- Srinivas Katkoori, Ph.D.
- Sriram Chellappan, Ph.D.
- Hao Zheng, Ph.D.
Subjects
dc:subject × 4Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.usf.edu/etd/6936