Small Screens and Large Graphs: Area-Effcient Drawings of Planar Combinatorial Structures

Abstract

Small Screens and Large Graphs: Area-Efficient Drawings of Planar Combinatorial Structures Fabrizio Frati Dipartimento di Informatica e Automazione - Roma Tre University Abstract Graphs are the most widely used data structures to represent relationships among objects. Maps, networks, circuits, molecules, compounds are a few examples of structures that are commonly represented by graphs. The clearest way to express the information conveyed in a graph is to visualize it. Namely, a drawing of a graph represents each object (in the graph terminology: vertex) of the graph as a point in the plane and each relationship (in the graph terminology: edge) between two objects as a line connecting the corresponding points. However, not every drawing can be regarded as a good representation of the graph. In fact, a drawing should be readable, that is, the human eye should be able to easily identify the relationships among the objects in the graph at the first glance to the drawing. Clearly, this is not a formal definition of what differentiates a good drawing from a bad drawing. However, a few topological and geometric features have been recognized and accepted as the criteria a drawing should satisfy in order to be readable. Planarity is probably the best characteristic a drawing can have. The absence of intersections between the edges of the graph allows a viewer to easily distinguish the line representing any edge and hence to immediately understand which are the vertices connected by the edge. From a geometric perspective, it would be preferable that edges are drawn as straight-lines, namely edges bending and repeatedly changing direction are detrimental for the readability of the drawing. When the straight-line requirement can not be met, it would be still desiderable to have edges drawn as poly-lines bending only a limited number of times. When the size of the graph to be represented is too large in order for the drawing to be constructed manually, there is a need for an algorithm automatically constructing such a drawing. Graph Drawing deals with the design of algorithms to automatically construct drawings of graphs. Usually a Graph Drawing algorithm takes as an input a graph, a set of requirements the drawing must satisfy (as being planar or having straight-line edges), and a set of aesthetics the drawing should satisfy as much as possible. The most important aesthetic a drawing should satisfy is probably the one of having a small area. In fact, automatic drawings usually have to be displayed on a computer screen of bounded size, hence they have to fit in the space available on the screen. The study of graph drawings in small area has been first motivated by the design of VLSI circuits and has attracted intense research efforts for almost thirty years now. In this thesis we deal with algorithms and bounds for drawing graphs in small area. We mainly deal with planar graphs (Part I of the thesis), series-parallel graphs and outerplanar graphs (Part II), trees (Part III), and clustered graphs (Part IV), and for each of these graph classes we consider the problem of obtaining drawings in small area under a large number of drawing conventions (e.g., straight-line, poly-line, orthogonal, upward). We design several algorithms for the construction of graph drawings in small area and we obtain lower bounds for the area requirements of several drawing styles. The graph classes and the drawing conventions we consider are among the most commonly used for applications. Nevertheless, the beauty of some combinatorial, topological, and geometric problems concerning the construction of graph drawings in small area justifies their study even when looking at them from a purely theoretical point of view. 1