Embeddings of Four-valent Framed Graphs into 2-surfaces

It is well known that the problem of detecting the least (highest) genus of a surface where a given graph can be embedded is closely connected to the problem of embedding special four-valent framed graphs, i.e. 4-valent graphs with opposite edge structure at vertices specified. This problem has been studied, and some cases (e.g., recognizing planarity) are known to have a polynomial solution. The aim of the present survey is to connect the problem above to several problems which arise in knot theory and combinatorics: Vassiliev invariants and weight systems coming from Lie algebras, Boolean matrices etc., and to give both partial solutions to the problem above and new formulations of it in the language of knot theory.