
ArcAdiA >
Tipologia di Documenti >
T  Tesi di dottorato >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/2307/503

Title:  Small Screens and Large Graphs: AreaEffcient Drawings of Planar Combinatorial Structures 
Authors:  Frati, Fabrizio 
Tutor:  Di, Battista Giuseppe 
Issue Date:  2Apr2009 
Publisher:  Università degli studi Roma Tre 
Abstract:  Small Screens and Large Graphs:
AreaEfficient 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 straightlines, namely edges
bending and repeatedly changing direction are detrimental for the readability of the drawing. When
the straightline requirement can not be met, it would be still desiderable to have edges drawn as
polylines 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 straightline 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), seriesparallel 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.,
straightline, polyline, 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 ...more 
URI:  http://hdl.handle.net/2307/503 
Appears in Collections:  X_Dipartimento di Informatica e automazione T  Tesi di dottorato

Files in This Item:
File 
Description 
Size  Format 
SmallScreensLargeGraphsFrati.pdf   2.93 MB  Adobe PDF   

This item is protected by original copyright

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
