A characterization of upper-embeddable graphs

Abstract

It is proved that a pseudograph <italic>G</italic> is upper-embeddable if and only if it has a spanning tree <italic>T</italic> such that <italic>G</italic> - <italic>T</italic> has at most one component with an odd number of edges. This result is then used to show that all 4-edge connected graphs are upper-embeddable.