Graph Orientation Structures and Their Applications

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

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.