A. A. Zykov [Fundamentals of Graph Theory, Nauka, Moscow, 1987] asks to determine, for a given closed surface $S$, all graphs $G$ (including disconnected ones) that admit an embedding $i\: G \hookrightarrow S$ in a closed surface $S$ leaving $S-i(G)$ connected. We anwser this question completely. For connected graphs the results can be formulated as follows: $G$ has an embedding $i\: G \hookrightarrow S$ with $S-i(G)$ connected if and only if $S$ is non-orientable and $\tilde\gamma(S) \geq \beta(G) = \vertE(G)\vert - \vertV(G)\vert + 1$, or $S$ is orientable and $\gamma(S) \geq \beta(G) - \gamma_M(G)$, where $\gamma_M(G)$ is the maximum genus of $G$.