Two graph problems are considered in this dissertation. A graph G with n vertices and m edges is a Laman graph, or equivalently a generically minimally rigid graph, if m = 2n - 3 and every induced subset of k vertices spans at most 2k - 3 edges. Laman graphs play a fundamental role in rigidity theory. We discuss the Verification problem: Given a graph G with n vertices, decide if it is Laman. We present an algorithm that recognizes Laman graphs in O(Tst(n) + n log n) time, where Tst (n) is the best time to extract two edge disjoint spanning trees from G. Our algorithm is based on a new data structure called red-black hierarchy and improves the previous O( Tst(n) + n2) algorithm. We also explore the properties of the red-black hierarchies and their use in computing inductive (Henneberg) constructions of Laman graphs.;The second problem considered is finding a shortest path in a geometric graph Rd , d = 2, 3, subject to the angle constraint on two adjacent segments of the path. We find the solution and use it for solving a polygonal chain simplification problem with a constraint on an angle between two consecutive segments of the output chain. Given a polygonal chain P in Rd , d = 2, 3, and a positive real value delta ∈ [0, pi/2) (or delta ∈ (pi/2, pi]), we give algorithms to approximate P by another polygonal chain P' such that the vertices of P' form an ordered subsequence of the vertices of P, P' stays "close" to P, the value of the turn angle between any two consecutive segments of P' is bounded (above or below) by delta, and the number of vertices of P' is minimized. This work closes the gap on the range of delta left in previous work on the problem. Our algorithm takes O(n2) time and space in R2 , and O(n2 log n) time, O(n2) space in R3 , matching the time and space complexities of the unconstrained problem.
展开▼
