Layanan keutuhan data (data integrity) dapat diperoleh dengan menggunakan fungsi hash kriptografis (cryptographic hash function). Sampai saat ini telah banyak konstruksi fungsi hash yang diusulkan oleh para kriptografer. Konstruksi pertama diusulkan oleh Ralph Merkle dan Ivan Damgård secara terpisah. Konstruksi ini disebut Konstruksi Merkle-Damgård. Selain konstruksi tersebut terdapat pula konstruksi fungsi hash yang berbasis pada teori graf. Konstruksi pertama diusulkan oleh Gilles Zemor pada tahun 1991. Konstruksi selanjutnya oleh Jean-Pierre Tillich pada tahun 1994. Pada makalah ini dibahas beberapa konstruksi fungsi hash yang berbasis teori graf, baik graf berarah maupun tidak berarah. Selain itu juga dibahas mengenai serangan-serangan terhadap konstruksi tersebut.