• Login
    View Item 
    •   etd@IISc
    • Division of Electrical, Electronics, and Computer Science (EECS)
    • Computer Science and Automation (CSA)
    • View Item
    •   etd@IISc
    • Division of Electrical, Electronics, and Computer Science (EECS)
    • Computer Science and Automation (CSA)
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Delaunay Graphs for Various Geometric Objects

    View/Open
    G26648.pdf (425.9Kb)
    Date
    2017-12-12
    Author
    Agrawal, Akanksha
    Metadata
    Show full item record
    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.
    URI
    https://etd.iisc.ac.in/handle/2005/2906
    Collections
    • Computer Science and Automation (CSA) [351]

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV
     

     

    Browse

    All of etd@IIScCommunities & CollectionsTitlesAuthorsAdvisorsSubjectsBy Thesis Submission DateThis CollectionTitlesAuthorsAdvisorsSubjectsBy Thesis Submission Date

    My Account

    LoginRegister

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV