Embeddings of four-valent framed graphs into two-surfaces

We study the problem of finding the minimal (maximal) genus for a surface where a given four-valent graph with fixed opposite edge structure can be embedded into. We find several partial relations and give new reformulations in combinatorial and knot theoretic languages.