skip to main content
Show Results with:

Realizability of graphs as triangle cover contact graphs

Sultana, Shaheena; Saidur Rahman, Md.

Theoretical computer science. Volume 720: (2018, April 11th); pp 24-35 -- Elsevier Science

Online access

  • Title:
    Realizability of graphs as triangle cover contact graphs
  • Author: Sultana, Shaheena;
    Saidur Rahman, Md.
  • Found In: Theoretical computer science. Volume 720: (2018, April 11th); pp 24-35
  • Journal Title: Theoretical computer science
  • Subjects: Teoretisk databehandling--Tidsskrifter; Automates mathématiques, Théorie des--Périodiques; Langages formels--Périodiques; Robots--Périodiques; Computer science--Periodicals--Mathematics; Electronic journals; Formal languages--Periodicals; Machine theory--Periodicals; Robots--Periodicals; Formal languages; Machine theory; Periodicals; Robots; Cover contact graph--Triangle cover contact graph--Realization problem; Dewey: 004.015105
  • Rights: Licensed
  • Publication Details: Elsevier Science
  • Abstract: Abstract LetS={p1, p2, , pn}be a set of pairwise disjoint geometric objects of some type and letC={c1, c2, , cn}be a set of closed objects of some type with the property that each element in C covers exactly one element in S and any two elements in C can intersect only on their boundaries. We call an element in S a seed and an element in C a cover . A cover contact graph (CCG) consists of a set of vertices and a set of edges where each of the vertex corresponds to each of the covers and each edge corresponds to a connection between two covers if and only if they touch at their boundaries. A triangle cover contact graph ( TCCG ) is a cover contact graph whose cover elements are triangles. In this paper, we show that every Halin graph has a realization as aTCCGon a given set of collinear seeds. We introduce a new class of graphs which we call super-Halin graphs. We also show that the classes super-Halin graphs, cubic planar Hamiltonian graphs anda×bgrid graphs have realizations asTCCGs on collinear seeds. We also show that some non-planar graphs have planar realizations asTCCGs. Every complete graph and clique-3 graph have realizations asTCCGs on any given set of seeds. Note that only trees and cycles are known to be realizable as CCG s and outerplanar graphs are known to be realizable asTCCGs.
  • Identifier: System Number: ETOCvdc_100063803465.0x000001; Journal ISSN: 0304-3975; 10.1016/j.tcs.2018.02.027
  • Publication Date: 2018
  • Physical Description: Electronic
  • Shelfmark(s): 8814.556000
  • UIN: ETOCvdc_100063803465.0x000001

Searching Remote Databases, Please Wait