Structural and Algorithmic Problems in Topological Graph Theory (Mathematics)

拓扑图论中的结构和算法问题（数学）

• 批准号: 8901458
• 负责人: Joan Hutchinson
• 金额: $ 6.2万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-07-01 至 1990-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8901458&HistoricalAwards=false
• 关键词: Structural; Algorithmic; Problems; Topological; Graph

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.

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