Relational information represented by graphs can be found in various areas. Understanding completely connected groups of items is useful in studying relational information. However, when displayed in the form of a graph drawing, completely connected graphs contain quadratically many edges relative to the number of their vertices. This may increase the difficulty in identifying useful information, such as maximal cliques, in the graph. This thesis attempts to display the maximal cliques and the cliques contained in two or more maximal cliques in a given graph in an explicit and clear fashion. In order to achieve the goal, the thesis defines two models, the clique-star and the reduced-clique-star, that represent given input graphs. Both representations reduce the number of edges of the original graphs while maintaining the information about the maximal cliques. This thesis shows that six classes of graphs that can be represented by planar clique-star representations, and four classes of graphs that can be represented by planar reduced-clique-star representations. It also empirically shows that small graphs or either very sparse or very dense graphs maybe beneficially represented by planar clique-star or planar reduced-clique-star representations.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:SSU.etd-09152010-164900 |
| Date | 19 September 2010 |
| Creators | Yamamoto, Yosuke |
| Contributors | Wu, Fangxiang, Dutchyn, Christopher, Keil, J. Mark, Cheston, Grant |
| Publisher | University of Saskatchewan |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://library.usask.ca/theses/available/etd-09152010-164900/ |
| Rights | unrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to University of Saskatchewan or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report. |
Page generated in 0.002 seconds