Date of Award
10-19-2015
Publication Type
Master Thesis
Degree Name
M.Sc.
Department
Computer Science
Keywords
Layer graph, Line rigid graph, Point placement problem, Rectangular drawing, Rigidity
Supervisor
Mukhopadhyay, Asish
Rights
info:eu-repo/semantics/openAccess
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Abstract
The point placement problem is to determine the position of n distinct points on a line, up to translation and reflection by fewest possible pairwise adversarial distance queries. This masters thesis focusses on two aspects of point placement problem. In one part we focusses on an experimental study of a number of deterministic point placement algorithms and an incremental randomized algorithm, with the goal of obtaining a greater insight into the behavior of these algorithms, particularly of the randomize algorithm. The pairwise distance queries in the point placement problem creates a type of graph, called point placement graph. A point placement graph G is dened as line rigid graph if and only if the vertices of G has unique placement on a line. The other part of this thesis focusses on recognizing line rigid graph of certain class based on structural property of an arbitrarily given graph. Layer graph drawing and rectangular drawing are used as key idea in recognizing line rigid graphs.
Recommended Citation
Sarker, Pijus Kumar, "Experiments with Point Placement Algorithms and Recognition of Line Rigid Graphs" (2015). Electronic Theses and Dissertations. 5450.
https://scholar.uwindsor.ca/etd/5450