Abstract:
For a set of geometric objects, the associative geometric intersection graph is the
graph with a vertex for each object and an edge between two vertices if and only if the
corresponding objects intersect. Geometric intersection graphs are very important
due to their theoretical properties and applicability. Based on the different geometric
objects, several types of geometric intersection graphs are defined. Given a graph G,
an induced (either vertex or edge) subgraph H µG is said to be an well-structured
subgraph if H satisfies certain properties among the vertices in H.
This thesis studies some well-structured subgraphs finding problems on various
geometric intersection graphs. We mainly focus on computational aspects of the
problems. In each problem, either we obtain polynomial-time exact algorithm or
show NP-hardness. In some cases, we also extend our study to design efficient
approximation algorithms and fixed-parameter tractable algorithms.
We study the construction of the planar Manhattan network (between every pair of
nodes there is a minimum-length rectilinear path) of linear size for a given convex
point set.
We consider the maximum bipartite subgraph problem, where given a set S of n
geometric objects in the plane, we want to compute a maximum-size subset S0 µ S
such that the intersection graph of the objects in S0 is bipartite.
We consider a variation of stabbing (hitting), dominating, and independent set problems
on intersection graphs of bounded faces of a planar subdivision induced by a set
of axis-parallel line segments in the plane.
We investigate the problem of finding a maximum cardinality uniquely restricted
matching (having no other matching that matches the same set of vertices) in proper
interval graphs and bipartite permutation graphs.
Finally, we consider the balanced connected subgraph problem on red-blue graphs (the
color of each vertex is either red or blue). Here the goal is to find a maximum-sized
induced connected subgraph that contains the same number of red and blue vertices.
