Astelnuovo-Mumford Regularity (simply regularity) measures the complexity of an object (e.g. ideal, module or sheaf) in algebraic geometry, commutative algebra and discrete geometry. In general, very little is known even in the case of square-free monomial ideals. By Stanley-Reisner theory, we can associate a simplicial complex to every square-free ideal, and such a simplicial complex can be regarded as an independence of a hypergraph. Regularity of a simplicial complex can be reformulated by the well-known Hochester's formula. If the generating monomials of a square-free ideal are quadratic, then the corresponding simplicial complex is the independence complex of a graph, and such an ideal is known as the edge ideal of the resulting graph. I will mainly talk about the regularity of edge ideals, and present our graph theoretical approach to the regularity. I shall present some graph invariants and structural properties that are related to the regularity. (This is a joint work with Yusuf Civan, Suleyman Demirel University)