Graph Orientation Structures and Their Applications

图的定向结构及其应用

• 批准号: 0728830
• 负责人: Huaming Zhang
• 金额: --
• 依托单位: University of Alabama in Huntsville
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-04-01 至 2011-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728830&HistoricalAwards=false
• 关键词: Graph; Orientation; Structures; Their; Applications

Given a graph G=(V,E), an orientation of G assigns a direction to every edge of G. Recent research indicates that the set of all the orientations satisfying certain predefined properties often possesses good combinatorial structures. For example, the set of all the orientations with prescribed out degree for each vertex of a plane graph G is a distributive lattice. Several such orientations and their respective combinatorial structures have been studied for plane graphs recently. Those combinatorial structures have been successfully used in understanding the properties of the studied graphs and in designing new efficient graph algorithms. They find applications in many fields such as graph drawing, information visualization, VLSI layout, etc. However, two main challenges exist in this field: (1) finding more combinatorial structures to a broader class of graphs, and (2) finding the implications of the combinatorial structures to the studied graphs. The principal investigator has recently obtained interesting results using various graph orientations. This research extends those results. The research activities include: (1) investigation on a special group of orientations of maximal bipartite plane graphs, which is somewhat related to the famous Barnette's conjecture, and hence may provide useful hints in solving this long-standing open problem, and (2) investigation on finding more combinatorial structures and their inter-relations to a broader class of graphs. In practice, the research is motivated by applications in graph drawing, information visualization, and VLSI layout problems. In theory, this research will discover novel combinatorial concepts, structures and algorithms for a broader class of graphs.

给定一个图G=（V，E），G的定向给G的每条边指定一个方向。最近的研究表明，满足某些预定义性质的所有方向的集合往往具有良好的组合结构。例如，一个平面图G的每个顶点具有规定出度的所有定向的集合是一个分配格。近年来，人们对平面图的几种定向及其组合结构进行了研究。这些组合结构已成功地用于理解所研究的图形的属性，并在设计新的高效的图形算法。他们发现在许多领域的应用，如图形绘制，信息可视化，超大规模集成电路布局等，然而，在这个领域存在两个主要的挑战：（1）找到更多的组合结构，以更广泛的一类图，（2）发现的组合结构的影响，研究的图。主要研究人员最近使用各种图形方向获得了有趣的结果。这项研究扩展了这些结果。研究活动包括：（1）研究极大二部平面图的一个特殊的方向群，它与著名的Barnette猜想有一定的联系，因此可能为解决这个长期存在的问题提供有用的线索;（2）研究寻找更多的组合结构及其与更广泛的图类的相互关系。在实践中，研究的动机是在图形绘制，信息可视化和超大规模集成电路布局问题的应用。在理论上，这项研究将发现新的组合概念，结构和算法的更广泛的一类图。