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