Information visualization: Orthogonal drawings of graphs.

摘要

Graphs are used extensively in key Computer Technology areas to model associative and structural information. Communicating this information clearly and effectively requires representing it on a graphics output device. Graph Drawing or Visualization studies the problem of automatic generation of nice and readable graphical representation (drawings) of graphs and networks. Typically, graphs are drawn on a 2-dimensional surface, vertices are represented by points, circles, or boxes, and edges are represented by continuous lines connecting their endpoints. In an orthogonal drawing edges are represented by polygonal chains consisting only of horizontal and vertical straight line segments. Given an n-vertex and m-edge graph of maximum degree four, we present a linear time algorithm based on vertex pairing to produce an orthogonal drawing of the graph with area at most 0.76 {dollar}nsp2{dollar}. Each edge has at most two bends for a total of {dollar}2n+2{dollar} bends for the whole drawing. In orthogonal drawings of graphs of degree higher than four, vertices are represented by rectangular boxes whose perimeter is less than twice their degree. Pairing vertices both ahead of time and during the drawing process produces drawings with good aspect ratio, maximum area {dollar}(m-1)times ({lcub}mover 2{rcub}+2){dollar}, and less than m bends, in O (m) time. We present two scenaria for interactive orthogonal graph drawing: No-Change and Relative-Coordinates. The former guarantees that the current drawing remains unaltered after an update operation, and the latter maintains the general shape of the current drawing. Experimentation with these two scenaria reveals that their average behavior is better than their theoretical one, and that Relative-Coordinates produces clear and compact drawings with few bends and crossings. Finally, we present two algorithms for 3-dimensional orthogonal graph drawing. For graphs of maximum degree six, the 3-D drawing is produced in linear time, has volume at most 4.66{dollar}nsp3{dollar} and allows at most three bends per edge. If the degree is higher, vertices are represented by solid 3-D boxes whose surface is proportional to their degree. The produced drawings have two bends per edge. Both algorithms guarantee no crossings and can be used under an interactive setting (i.e., vertices arrive on-line), as well.