Approximation algorithms for Graph Drawing

点击翻译按钮获取中文摘要

In applications such as social networks, street maps, entity-relationship diagrams for data bases, organizational hierarchies and control flow diagrams for software engineering, the underlying structure can be described abstractly as a graph: it consists of vertices (humans, sites, entities, employees, functions) and edges (relationships, streets, function calls) between them. Visualizing such graphs helps in analyzing their structure, for example for detecting clusters or similarities.  This motivates the problem of graph drawing: develop algorithms that automatically convert a graph into a picture that is easy to read.******User studies have shown that the most important criteria for legibility of a graph drawing is to minimize the number of crossings. Hence an important sub-area of graph drawing is how to draw a planar graph, i.e., a graph that could be drawn without any crossings at all. Many algorithms for drawing planar graphs exist, but although they are provably good with regard to some quality measure, they often give pictures that are far from best-possible for a given graph.******The topic of the proposed research is approximation algorithms for planar graph drawing, i.e., to develop algorithms with performance guarantees that are provably within a factor of the optimum for all graphs. Currently very few approximation algorithms for drawing planar graphs exist. Even the key ingredients for using well-known techniques for approximation algorithms (such as LP relaxation and Baker's technique) have rarely been studied.  I recently made progress on these key ingredients for the objective of minimizing the area, and plan to expand the work into developing approximation algorithms for minimum-area drawings  A major challenge for this is to develop new lower bound tools for planar graph drawing, since the existing lower-bound tools have proved insufficient for approximation algorithms.  Possibly no approximation algorithms exist, and so another avenue of my proposed research is to prove such impossibilites by applying the techniques of APX-hardness from complexity theory.  ***In the longer term, many other graph drawing objectives are used in the applications, and developing approximation algorithms for them is an exciting challenge. Such algorithms would give graph drawings that are provably not too far from the best-possible drawing of the given input graph, and hence should be a significant improvement for displaying the graph-structures of the above application areas.**