On the maximum number of cliques in a graph embedded in a surface

This paper studies the following question: given a surface σ and an integer n, what is the maximum number of cliques in an n-vertex graph embeddable in σ? We characterise the extremal graphs for this question, and prove that the answer is between 8(n-ω)+2 ω and 8n+5/2 2 ω+o(2 ω), where ω is the maximum integer such that the complete graph K ω embeds in σ. For the surfaces S 0, S 1, S 2, N 1, N 2, N 3 and N 4 we establish an exact answer. © 2011 David Wood.SCOPUS: ar.j