Show simple item record

dc.contributor.advisorGovindarajan, Sathish
dc.contributor.authorAgrawal, Akanksha
dc.date.accessioned2017-12-12T04:33:41Z
dc.date.accessioned2018-07-31T04:38:45Z
dc.date.available2017-12-12T04:33:41Z
dc.date.available2018-07-31T04:38:45Z
dc.date.issued2017-12-12
dc.date.submitted2014
dc.identifier.urihttp://etd.iisc.ac.in/handle/2005/2906
dc.identifier.abstracthttp://etd.iisc.ac.in/static/etd/abstracts/3768/G26648-Abs.pdfen_US
dc.description.abstractGiven 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.isoen_USen_US
dc.relation.ispartofseriesG26648en_US
dc.subjectDelaunay Triangulationen_US
dc.subjectDelaunay Graphsen_US
dc.subjectComputational Geometryen_US
dc.subjectVertex Coveren_US
dc.subjectTriangulationsen_US
dc.subjectAxis-Paralalel Slabsen_US
dc.subjectMaximal-Planar Graphsen_US
dc.subjectFixed Parameter Tractable Algorithmsen_US
dc.subjectHitting Seten_US
dc.subjectNP-completenessen_US
dc.subjectChordless-NSTen_US
dc.subjectGeometric Objectsen_US
dc.subject.classificationComputer Scienceen_US
dc.titleDelaunay Graphs for Various Geometric Objectsen_US
dc.typeThesisen_US
dc.degree.nameMSc Enggen_US
dc.degree.levelMastersen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record