dc.contributor.advisor Govindarajan, Sathish dc.contributor.author Agrawal, Akanksha dc.date.accessioned 2017-12-12T04:33:41Z dc.date.accessioned 2018-07-31T04:38:45Z dc.date.available 2017-12-12T04:33:41Z dc.date.available 2018-07-31T04:38:45Z dc.date.issued 2017-12-12 dc.date.submitted 2014 dc.identifier.uri http://etd.iisc.ac.in/handle/2005/2906 dc.identifier.abstract http://etd.iisc.ac.in/static/etd/abstracts/3768/G26648-Abs.pdf en_US dc.description.abstract Given a set of n points P ⊂ R2, the Delaunay graph of P for a family of geometric objects C is a graph defined as follows: the vertex set is P and two points p, p' ∈ P are connected by an edge if and only if there exists some C ∈ C containing p, p' but no other point of P. Delaunay graph of circle is often called as Delaunay triangulation as each of its inner face is a triangle if no three points are co-linear and no four points are co-circular. The dual of the Delaunay triangulation is the Voronoi diagram, which is a well studied structure. The study of graph theoretic properties on Delaunay graphs was motivated by its application to wireless sensor networks, meshing, computer vision, computer graphics, computational geometry, height interpolation, etc. The problem of finding an optimal vertex cover on a graph is a classical NP-hard problem. In this thesis we focus on the vertex cover problem on Delaunay graphs for geometric objects like axis-parallel slabs and circles(Delaunay triangulation). 1. We consider the vertex cover problem on Delaunay graph of axis-parallel slabs. It turns out that the Delaunay graph of axis-parallel slabs has a very special property — its edge set is the union of two Hamiltonian paths. Thus, our problem reduces to solving vertex cover on the class of graphs whose edge set is simply the union of two Hamiltonian Paths. We refer to such a graph as a braid graph. Despite the appealing structure, we show that deciding k-vertex cover on braid graphs is NP-complete. This involves a rather intricate reduction from the problem of finding a vertex cover on 2-connected cubic planar graphs. 2. Having established the NP-hardness of the vertex cover problem on braid graphs, we pursue the question of improved fixed parameter algorithms on braid graphs. The best-known algorithm for vertex cover on general graphs has a running time of O(1.2738k + kn) [CKX10]. We propose a branching based fixed parameter tractable algorithm with running time O⋆(1.2637k) for graphs with maximum degree bounded by four. This improves the best known algorithm for this class, which surprisingly has been no better than the algorithm for general graphs. Note that this implies faster algorithms for the class of braid graphs (since they have maximum degree at most four). 3. A triangulation is a 2-connected plane graph in which all the faces except possibly the outer face are triangles, we often refer to such graphs as triangulated graphs. A chordless-NST is a triangulation that does not have chords or separating triangles (non-facial triangles). We focus on the computational problem of optimal vertex covers on triangulations, specifically chordless-NST. We call a triangulation Delaunay realizable if it is combinatorially equivalent to some Delaunay triangulation. Characterizations of Delaunay triangulations have been well studied in graph theory. Dillencourt and Smith [DS96] showed that chordless-NSTs are Delaunay realizable. We show that for chordless-NST, deciding the vertex cover problem is NP-complete. We prove this by giving a reduction from vertex cover on 3-connected, triangle free planar graph to an instance of vertex cover on a chordless-NST. 4. If the outer face of a triangulation is also a triangle, then it is called a maximal planar graph. We prove that the vertex cover problem is NP-complete on maximal planar graphs by reducing an instance of vertex cover on a triangulated graph to an instance of vertex cover on a maximal planar graph. en_US dc.language.iso en_US en_US dc.relation.ispartofseries G26648 en_US dc.subject Delaunay Triangulation en_US dc.subject Delaunay Graphs en_US dc.subject Computational Geometry en_US dc.subject Vertex Cover en_US dc.subject Triangulations en_US dc.subject Axis-Paralalel Slabs en_US dc.subject Maximal-Planar Graphs en_US dc.subject Fixed Parameter Tractable Algorithms en_US dc.subject Hitting Set en_US dc.subject NP-completeness en_US dc.subject Chordless-NST en_US dc.subject Geometric Objects en_US dc.subject.classification Computer Science en_US dc.title Delaunay Graphs for Various Geometric Objects en_US dc.type Thesis en_US dc.degree.name MSc Engg en_US dc.degree.level Masters en_US dc.degree.discipline Faculty of Engineering en_US
﻿