Mathematical Sciences: Structural Graph Theory

数学科学：结构图论

• 批准号: 9623031
• 负责人: Robin Thomas
• 金额: $ 13.12万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-06-15 至 2000-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9623031&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Structural; Graph; Theory

Thomas 9623031 Thomas will carry out and supervise research in graph theory with emphasis on structural characterizations of various properties of graphs. Thomas will also develop efficient practical algorithms based on this research. The areas of interest are Hadwiger's conjecture, spatial embeddings of graphs, applications of graph theory to low-dimensional topology, generalizations of the four-color theorem, graphs on surfaces with particular emphasis on coloring and hamiltonicity, linkage and subdivision problems, and infinite graphs. Graph theory is a subdiscipline of combinatorics. Combinatorics attempts to find efficient methods to study how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research. In addition, enumerative information from combinatorics research has been of use in the design of geometric algorithms for problems in robotics and motion planning.

Thomas将进行和指导图论的研究，重点是图的各种性质的结构表征。Thomas还将在此基础上开发高效实用的算法。感兴趣的领域是哈德维格猜想，图的空间嵌入，图论在低维拓扑中的应用，四色定理的推广，特别强调着色和哈密性的曲面图，连杆和细分问题，以及无限图。图论是组合学的一个分支学科。组合学试图找到有效的方法来研究离散的对象集合如何排列。离散系统的行为对现代通信极为重要。例如，大型网络的设计，比如那些出现在电话系统中的网络，以及计算机科学中处理离散对象集的算法设计，这就利用了组合研究。此外，从组合学研究中获得的枚举信息已被用于机器人和运动规划问题的几何算法设计。