Set labelling vertices and study of auxiliary graphs

Abstract

quotGiven a set of nonempty subsets of some universal set, their intersection graph is defined as the graph with one vertex for each set and two vertices are adjacent precisely when their representing sets have non-empty intersection. Sometimes these sets are finite, but in many well known examples like geometric graphs (including interval graphs) they are infinite. One can also study the reverse problem of expressing the vertices of a given graph as distinct sets in such a way that adjacency newlinecoincides with intersection of the corresponding sets. The sets are usually required to conform to some template, depending on the problem, to be either a finite set, or some geometric set like intervals, circles, discs, cubes etc. 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. In this thesis, 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 newlineviewing 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). newline newlineWe propose two applications related to information visualization which use newlinethe same underlying idea: assignment of unique labels to each vertex of a graph (or tree) and removal of all edges. A pair of nodes is adjacent if and only if their corresponding labels are disjoint. The proposed newlinelabelling scheme can be used to establish isomorphism and study of ontologies. newline newlineInformation visualization is a class of techniques which is used to present data in a graphical or pictorial format.