Graph Encodings, Embeddings, Labelings and Applications
Xin He Principal Investigator
MetadataShow full item record
In all graph algorithms, graphs are encoded by binary strings.<br/>The problem of encoding graphs by binary strings is a fundamental<br/>problem in computer science. To be useful in graph algorithms,<br/>an encoding of a graph G should be as short as possible and<br/>support various graph queries and operations. The well known<br/>adjacency-matrix and adjacency-lists representations are used by<br/>virtually all existing graph algorithms. However, they do not satisfy<br/>all of these requirements. New graph encoding schemes satisfying all<br/>of these requirements for various graph families will be developed.<br/>Once such an encoding scheme for a graph family is found, it will be<br/>possible to improve and/or simplify existing algorithms for solving<br/>problems on this graph family. In addition to graph algorithms, the<br/>short encoding of plane triangulations (i.e. triangular meshes) has<br/>important applications in Computer Graphics.<br/><br/>A planar graph may have many plane embeddings. For some applications,<br/>it is often required to find an embedding such that certain properties<br/>are satisfied. These problems arise from areas such as VLSI design,<br/>Geographic Information Systems, and some graph optimization problems.<br/>Existing algorithms for solving these problems rely on dynamic<br/>programming and are not efficient. In this research project we will<br/>develop more efficient algorithms and explore their applications.<br/><br/>A common technique is used in several recent algorithms for solving<br/>graph drawing and floor-planning problems: Labeling vertices or edges<br/>of a graph so that certain regular properties are satisfied; then<br/>solving the problems by using the combinatorial structures resulting<br/>from the labeling. We will extend this technique and use it to solve<br/>other problems in these fields.