Mahipal Jadeja, PhD

Summary of Ph.D. work: 

The problem of representing a graph as an intersection graph of sets was first introduced by Erdos et al. and they looked at minimising the underlying universal set necessary to represent any given graph. In that paper, it was shown that the problem is NP complete. We study a natural variant of this problem which is to consider graphs where vertices represent distinct sets and adjacency coincides with disjointness. Although this is nearly the same problem on the complement graph, for specific families of graphs this is a more natural way of viewing it. The parameters we take into account are the minimum universe size possible (USN), the minimum individual label size possible (ILN) and their uniform versions (UUSN and UILN respectively).  The work done for the thesis can be enumerated under the following broad headings. 

 

1. Results (either exact or asymptotic) on USN, UUSN and ILN for some special families of graphs. 

2. Study of data integration, dynamic queries, key features etc of tree-map (a visualization tool for large data). 

3. Labeled object treemap: a new graph-labelling based technique for visualizing multiple hierarchies. 

4. Edgeless Graph: a new graph based information visualization technique. 

5. A new characterisation of total graphs and spanning tree auxiliary graphs.