Morphing and visiting drawings of graphs

Abstract

Among the most widely used data structures to represent pairwise relationships between entities, graphs play a key role. Graph applications can, indeed, be found in every field, ranging from maps to circuits, and from networks to interpersonal relationships. Visualizing a graph is probably one of the most expressive ways to describe the information encoded in it. Such an issue is addressed in the research field of Graph Drawing, which inherits techniques from the areas of Graph Theory, Graph Algorithms, and Computational Geometry. Namely, in a drawing of a graph each entity -called vertex - is usually represented by a point in the plane and each relationship -called edge- between two entities as a curve connecting the corresponding points. Clearly, not every drawing can be considered a good representation of the graph. Vertices and edges should be drawn in such a way that the human eye is facilitated in identifying the relationships among the entities at a glance. Namely, the drawing should be readable. During the years, some topological and geometric features that a drawing should satisfy in order to be easily readable have been recognized and formally characterized. The main goals of Graph Drawings are, then, creating algorithms that automatically produce drawings respecting such criteria and, possibly, defining new ones. Planarity, that is the absence of partial or total overlapping among vertices and edges, is proba- bly the most natural and desirable characteristic a drawing can have, as it allows a viewer to easily distinguish the curve used to represent any edge-relationship and hence to immediately recognize which entities-vertices participate in that relationship. Unfortunately, due to their topological structure, not all the graphs admit a planar drawing. In such cases, a natural requirement for the drawing is that of containing as few crossings as possible. Moreover, especially if the input graph -and hence the area of the drawing- is large, it is convenient that the points where two edges cross are easily distinguishable from the points where vertices are placed. Observe that, while planarity is a property that a drawing may ful ll or not, the area and the number of crossings are two examples of measure of quality that can be used to compare two drawings of the same graph. From the geometric point of view, it would be preferable that edges are drawn as straight- lines. Edges that bend and repeatedly or abruptly change direction might sensibly decrease the readability of the drawing. In straight-line drawings, however, the information of interest for a user might not be sufficiently emphasized. In that case, edges can be represented as poly-lines bending only a limited number of times or having a limited number of slopes, so that the negative impact on the readability of the drawing is limited. Other required features for a drawing of a graph to describe some meta-information, we recall the representation of groups (called clusters) of vertices that, aside from the relationship described by the edges, represent objects that share some properties, as in the case of clustered graphs. Also, in some contexts it might be required to emphasize the chains of relationships that indirectly involve pairs of entities. In this case, the placement of the vertices and the fashion in which edges are drawn should be able to \lead" the eye of a viewer from an object to another through the chain of relationships that are of interest. Of course, some of such desired features can be in contrast with each other and hence cannot be simultaneously satisfied by a single drawing. It is easy to imagine contexts in which several drawings of the same graph, which can be substantially different from each other, are of interest to the same observer. Due to the great difference between two drawings, a considerable effort might be required to the user, while switching from one drawing to another, in \updating" the mental map he or she has of the graph. In order to support the user in this operation, a smooth transformation of a drawing into another might be desirable. Clearly, since the purpose of this transformation is to support the user in changing the focus from a drawing to another, it should introduce as few distracting elements, e.g. crossings, bends in the edges, or non-linear trajectories, as possible. In this thesis we mainly deal with algorithms that compute planar linear morphs, i.e., trans- formations, of planar drawings of the same graph in which planarity is preserved at any time and vertices move at uniform speed along straight-line trajectories. We also consider the problem of constructing drawings that, at the same time, emphasize certain properties of a given graph and require small area. We mainly deal with planar embedded graphs, namely, graphs in which the circular order of the edges around each vertex is xed and such that there exists a planar drawing of the graph in which such an order is maintained. In Part I we present an algorithm for the construction of planar linear morphs of series-parallel graphs with a number of moves that is linear in the size of the graph, prove that such an algorithm is asymptotically optimal by providing a lower bound on the number of linear moves that are required to transform a planar drawing of a plane graph, and give an algorithm for constructing planar linear morphs of general plane graphs with a number of moves that is quadratic in the size of the graph. In Part II we consider the problem of computing drawings of graphs in which some features, namely chains of relationships between pairs of vertices and the difference between vertices and crossings in drawings of non-planar graphs, are emphasized, thus allowing the user to easily \visit" the underlying graph.