The class of planar graphs and planar meshes is a well-studied graph class. It has been a driving force in the field of graph algorithms. Although it has been the research subject in graph theory and algorithm design for many years, it is striking that many interesting properties, combinatorial structures, and applications of this class have been discovered in recent years. These discoveries have important and sometimes unexpected applications in fields such as graph drawing, VLSI layout, computer graphics etc. The PI proposes to develop new algorithms for this important graph class and investigate their applications.
The PI has obtained interesting results in this field in the past few years. The 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, 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 an advanced algorithm course.
