Graphs that have two disjoint noncontractible cycles in every possible
embedding in surfaces are characterized. Similar characterization is
given for the class of graphs whose orientable embeddings (embeddings
in surfaces different from the projective plane, respectively) always
have two disjoint noncontractible cycles. For graphs which admit embed
dings in closed surfaces without having two disjoint noncontractible c
ycles, such embeddings are structurally characterized. (C) 1996 Academ
ic Press, Inc.