| Visualization of large graphs is difficult given the constraints imposed by the current technology (limited number of pixels on a screen) and the complexity of the graphs to be displayed (millions of nodes and edges). We present an algorithm for displaying large graphs based on clustering: the graph is decomposed into a logarithmic number of levels, such that each level represents the graph in more detail. The graph can be displayed using a multi-level or a fisheye drawing so as to convey its global structure and show the local structure in an area of interest. The algorithm runs in O( n log n + m + D 0(G)), where n and m are the number of vertices and edges of the graph G, and D0(G) is the time for an initial embedding of G in the plane.; We then present a cluster-based drawing approach for planar graphs that produces a c-planar clustering. Using the clustering, we obtain a representation of the graph as a collection of O(log n) levels, where each succeeding level represents the graph in an increasing level of detail. At the same time, the difference between two graphs on neighboring levels of the hierarchy is small, thus preserving the viewer's mental map. The running time of the algorithm is O(n log n).; We also address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present an algorithm for drawing n-vertex planar graphs such that the edges are sequences of two continuous circular arcs. The algorithm runs in O(n) time, embeds the graph on an O(n) × O(n) grid, and maintains Θ(1/d(v)) angular resolution. This is also the first algorithm to simultaneously achieve good angular resolution, small area and one bend per edge using straight-line segments. |
