Approximation algorithms for graph problems

This thesis studies approximation algorithms for two fundamental problems arising in graph theory: counting copies of one graph in another graph and estimating distances in geometric graphs.;In the first part of this thesis, we look at the problem of counting the number of copies of one (template) graph in another (base) graph. This is the counting version of the subgraph isomorphism problem and is ;In the second part of this thesis, we present algorithms for constructing approximate sparse representations of geometric intersection graphs. Given a collection of geometric objects, their intersection graph is an undirected graph that has one vertex per object, and connects two objects by an edge whenever the intersection of the two objects is nonempty. A disk graph is an intersection graph of a set of disks with arbitrary radii in the plane (the generalization to higher dimensions is known as a ball graph). We present the first algorithm for constructing sparse (1 + epsilon)-spanners for ball graphs. The algorithm takes sub-quadratic time. For the special case where all the balls have the same radius, we show that the spanner construction has complexity almost equivalent to the construction of a Euclidean minimum spanning tree. We also present efficient algorithms for answering approximate distance queries in ball graphs. Disk graphs have been widely used to model wireless ad hoc networks. Spanners and distance queries are used for topology control and routing in these networks.