Articulo
Cliques and extended triangles : A necessary condition for planar clique graphs
Autor
Alcón, Liliana Graciela
Gutiérrez, Marisa
Institución
Resumen
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 Szwarcfiter 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(n2) time. Facultad de Ciencias Exactas