The complexity of cover graph recognition for some varieties of finite lattices

We address the following decision problem: Instance: an undirected graphG. Problem: IsG a cover graph of a lattice? We prove that this problem is NP-complete. This extends results of Brightwell 5] and Ne?et?il and Rödl 12]. On the other hand, it follows from Alvarez theorem 2] that recognizing cover graphs of modular or distributive lattices is in P. An important tool in the proof of the first result is the following statement which may be of independent interest: Given an integerl, l?3, there exists an algorithm which for a graphG withn vertices yields, in time polynomial inn, a graphH with the number of vertices polynomial inn, and satisfying girth(H)?l and χ(H)=χ(G).