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

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 p...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2004-05, Vol.141 (1), p.3-17
Main Authors: Alcón, Liliana, Gutierrez, Marisa
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Clique graphs
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Extended triangles
Graph theory
Helly graphs
Mathematics
Planar graphs
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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( n 2) time.
ISSN:0166-218X
1872-6771
DOI:10.1016/S0166-218X(03)00369-X