University of SaskatchewanHARVEST
  • Login
  • Submit Your Work
  • About
    • About HARVEST
    • Guidelines
    • Browse
      • All of HARVEST
      • Communities & Collections
      • By Issue Date
      • Authors
      • Titles
      • Subjects
      • This Collection
      • By Issue Date
      • Authors
      • Titles
      • Subjects
    • My Account
      • Login
      JavaScript is disabled for your browser. Some features of this site may not work without it.
      View Item 
      • HARVEST
      • Electronic Theses and Dissertations
      • Graduate Theses and Dissertations
      • View Item
      • HARVEST
      • Electronic Theses and Dissertations
      • Graduate Theses and Dissertations
      • View Item

      Displaying cliques in graph drawings

      Thumbnail
      View/Open
      YosukeMScThesis.pdf (3.379Mb)
      Date
      2010-09-19
      Author
      Yamamoto, Yosuke
      Type
      Thesis
      Degree Level
      Masters
      Metadata
      Show full item record
      Abstract
      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.
      Degree
      Master of Science (M.Sc.)
      Department
      Computer Science
      Program
      Computer Science
      Supervisor
      Keil, J. Mark
      Committee
      Wu, Fangxiang; Dutchyn, Christopher; Cheston, Grant
      Copyright Date
      September 2010
      URI
      http://hdl.handle.net/10388/etd-09152010-164900
      Subject
      confluent drawing
      planar drawing
      star
      Collections
      • Graduate Theses and Dissertations
      University of Saskatchewan

      University Library

      © University of Saskatchewan
      Contact Us | Disclaimer | Privacy