Structural and Algorithmic Problems in Topological Graph Theory (Mathematics)

在图论的数学领域，有限构型及其相互联系的研究，以及计算机科学中组合（有限）算法的理论研究之间，存在着越来越多的互利关系。本研究的重点是拓扑图理论，这是一个由这些相互关系特别增强的领域：这个领域和这个提议，特别是考虑在表面（球体加手柄）上嵌入（或绘制）图，并寻求抽象和算法问题的解决方案。该项目将扩展关于嵌入图中不可收缩循环的知识，以及关于移除减少属数或重复删除后留下平面图的顶点集的知识。这些结构的结果将导致其他嵌入参数的信息，如厚度和布局，并将尝试扩展关于已知的平面图的结果，例如，在图着色和嵌入算法领域。互动活动包括：教授组合理论专题课程；在数学系每周的组合学研讨会上举办一系列研讨会并邀请一些杰出的女性组合学研究人员参加该研讨会；并举办一到两个小组讨论，包括西北地区的女性数学研究人员，主题是“女性在数学领域的一些经验”和“如何成为一名研究数学家”。该项目进一步推进了VPW计划的目标，即(1)为女性提供在工程和NSF支持的科学学科中发展职业的机会；(2)通过为在工业、政府和学术机构工作的女性科学家和工程师提供更大的知名度，鼓励女性在科学和工程领域追求职业。通过鼓励妇女参与科学，这是对国家未来科学活力的宝贵投资。

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.