Computing well-structured subgraphs in geometric intersection graphs/ Satyabrata Jana

Thesis (Ph.D.) - Indian Statistical Institute, 2021

Includes bibliography

1. Introduction -- 2. Preliminaries -- 3. Review and related works -- 4. Manhattan Network for Convex Point Sets -- 5. Maximum Bipartite Subgraphs -- 6. Rectilinear Subdivision -- 7. Uniquely Restricted Matching -- 8. Balanced Connected Subgraph -- 9. Conclusion

Guided by Prof. Sasanka Roy

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 S
0 ⊆ S
such that the intersection graph of the objects in S
0
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.