amount of time that is polynomial per generated clique. An algorithm such as theirs in which the running time depends on the output size is known as an output-sensitive algorithm. Their algorithm is based on the following two observations, relating the maximal cliques of the given graph to the maximal cliques of a graph formed by removing an arbitrary vertex from : For every maximal clique of , either continues to form a maximal clique in , or forms a maximal clique in . Therefore, has at least as many maximal cliques as does. Each maximal clique in that does not contain is a maximal clique in , and each maximal clique in that does contain can be formed from a maximal clique in by adding and removing the non-neighbors of from . Using these observations they can generate all maximal cliques in by a recursive algorithm that chooses a vertex arbitrarily and then, for each maximal clique in , outputs both and the clique formed by adding to and removing the non-neighbors of . However, some cliques of may be generated in this way from more than one parent clique of , so they eliminate duplicates by outputting a clique in only when its parent in is lexicographically maximum among all possible parent cliques. On the basis of this principle, they show that all maximal cliques in may be generated in time per clique, where is the number of edges in and is the number of vertices. improve this to per clique, where is the arboricity of the given graph. provide an alternative output-sensitive algorithm based on fast matrix multiplication. show that it is even possible to list all maximal cliques in lexicographic order with polynomial delay per clique. However, the choice of ordering is important for the efficiency of this algorithm: for the reverse of this order, there is no polynomial-delay algorithm unless P = NP. On the basis of this result, it is possible to list all maximal cliques in polynomial time, for families of graphs in which the number of cliques is polynomially bounded. These families include chordal graphs, complete graphs, triangle-free graphs, interval graphs, graphs of bounded boxicity, and planar graphs. In particular, the planar graphs have cliques, of at most constant size, that can be listed in linear time. The same is true for any family of graphs that is both sparse (having a