Graph Orientation Structures and 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.