All Questions

Given a graph $G$, there is a minimal integer $g$ associated with it which captures the minimum genus a surface needs to have so that $G$ embeds in the surface without edge crossings. Is there a way ...

In the following paper by Valiant http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf He shows under theorem 2 (at the bottom of the second page) that any planar graph $G$ of degree 3 or 4 ...