This thesis reviews the establishment of the link between knot theory and graph theory. The Chromatic polynomial, the dichromatic polynomial and the Tutte polynomial are examined in detail as graph invariants related to the vertex coloring of a graph. Signed planar graphs are one-to-one correspondence with links and knots via medial construction. This correspondence reveals the relation between the Tutte polynomial and Kaufmann bracket polynomial, hence a Jones polynomial. Furthermore, we explore Virtual Knot Theory, introduced by Kauffman, which generalizes classical knot theory. The Bollobás-Riordan polynomial is presented as a generalization of the Tutte polynomial for ribbongraphs. We show the relationship between the Kauffman bracket polynomials of virtual links and the Bollobás-Riordan polynomials of ribbon graphs.