There has been increasing, mutual benefit between the mathematical field of graph theory, a study of finite configurations and their interconnections, and the theoretical study in computer science of combinatorial (finite) algorithms. This research focuses on topological graph theory, an area particularly enhanced by these interrelations: this field and this proposal, in particular, consider the embedding (or drawing) of graphs on surfaces (the sphere plus handles) and seeks solutions to questions both abstract and algorithmic. The project will extend knowledge about noncontractible cycles in embedded graphs and about sets of vertices whose removal decreases the genus or after repeated deletion leaves a planar graph. Results on these structures would lead to information on other embedding parameters, such as thickness and layout, and would try to extend results about the well-understood planar graphs, for example, in the areas of graph colorings and embedding algorithms. The interactive activities include teaching a topics course in combinatorial theory; giving a series of seminars in the mathematics department's weekly combinatorics seminar and inviting a number of distinguished women combinatorics researchers to that seminar; and presenting one or two panels, including Northwest-area women mathematics researchers, on "Some experiences of women in mathematics" and "On being a research mathematician." This project furthers VPW program objectives which are (1) to provide opportunities for women to advance their careers in engineering and in the disciplines of science supported by NSF and (2) to encourage women to pursue careers in science and engineering by providing greater visibility for women scientists and engineers employed in industry, government, and academic institutions. By encouraging the participation of women in science, it is a valuable investment in the Nation's future scientific vitality.
