Cliques and extended triangles. A necessary condition for planar clique graphs

✍ Scribed by Liliana Alcón; Marisa Gutierrez

• Book ID: 104294269
• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 256 KB
• Volume: 141
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00369-x

✦ Synopsis

By generalizing the idea of extended triangle of a graph, we succeed in obtaining a common framework for the result of Roberts and Spencer about clique graphs and the one of Szwarcÿter about Helly graphs. We characterize Helly and 3-Helly planar graphs using extended triangles. We prove that if a planar graph G is a clique graph, then every extended triangle of G must be a clique graph. Finally, we show the extended triangles of a planar graph which are clique graphs. Any one of the obtained characterizations are tested in O(n 2 ) time.