Please use this identifier to cite or link to this item: http://hdl.handle.net/10603/194491
Title: Set labelling vertices and study of auxiliary graphs
Researcher: Jadeja, mahipal
Guide(s): Rahul Muthu
Keywords: Graph Visualization
Object Treemap
Set labelling
intersection number
vertex labelling
Information visualization
Taxonomy
social network analysis,
University: Dhirubhai Ambani Institute of Information and Communication Technology (DA-IICT)
Completed Date: February 2018
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.
Pagination: xv, 164 p.
URI: http://hdl.handle.net/10603/194491
Appears in Departments:Department of Information and Communication Technology

Files in This Item:
File Description SizeFormat 
01_title.pdfAttached File82.44 kBAdobe PDFView/Open
02_declaration and certificate.pdf81.15 kBAdobe PDFView/Open
03_acknowledgements.pdf60.98 kBAdobe PDFView/Open
04_contents.pdf119.76 kBAdobe PDFView/Open
05_abstract.pdf94.38 kBAdobe PDFView/Open
06_list of table.pdf58.07 kBAdobe PDFView/Open
07_list of figures.pdf141.9 kBAdobe PDFView/Open
08_chapter 1.pdf275.27 kBAdobe PDFView/Open
09_chapter 2.pdf1.29 MBAdobe PDFView/Open
10_chapter 3.pdf978.05 kBAdobe PDFView/Open
11_chapter 4.pdf460.33 kBAdobe PDFView/Open
12_chapter 5.pdf566.04 kBAdobe PDFView/Open
13_chapter 6.pdf443.02 kBAdobe PDFView/Open
14_chapter 7.pdf337.51 kBAdobe PDFView/Open
15_chapter 8.pdf154.1 kBAdobe PDFView/Open
16_bibliography.pdf102.66 kBAdobe PDFView/Open


Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.