SPANNING PLANAR SUBGRAPHS OF GRAPHS IN THE TORUS AND KLEIN BOTTLE

There are two main purposes of this article. First we show that every 3-connected graph embedded in the torus or the Klein bottle has a span ning planar subgraph which is 2-connected, and in fact has a slightly stronger connectivity property. Second, this subgraph is applied to sh ow that every 3-connected graph that embeds in the torus or Klein bott le has both a 2-walk (a closed walk visiting every vertex exactly once or twice) and a 3-tree (a spanning tree with maximum degree at most 3 ). This completes the characterization of surfaces for which every emb edded 3-connected graph has a 2-walk (or 3-tree). (C) 1995 Academic Pr ess, Inc.