Graph Orientation and Applications

Given a graph G=(V,E), an orientation O of G is an assignment of directions to the edges of G. We may require that certain properties must be satisfied by O. Varying the requirements, different orientations can be defined. The orientations with special properties often result in interesting combinatorial structures. Recently, several orientations of planar graphs have been studied. They have important and sometimes unexpected applications in fields such as graph drawing, VLSI layout, computer graphics etc. These orientations often lead to elegant algorithms, which either improve or simplify previously known algorithms. The intellectual merit: The PI has recently obtained interesting results using various orientations. The proposed research extends these results. The proposed project will result in novel combinatorial concepts and constructions and new algorithmic tools. This research will make both theoretical and practical contributions. On the theoretical side, several important open questions in graph theory and combinatorics are among the proposed problems. On the practical side, many problems discussed in the proposal are motivated by applications in graph drawing, computer graphics and VLSI layout problems. The broader impacts: The results obtained from this research will have impacts on practical fields such as graph drawing, computer graphics and VLSI design, by providing better, simpler and more efficient algorithms. It will also enhance graduate education in computer science. The algorithms, concepts and techniques developed in this research will be include in a new advanced algorithm course.