ArcAdiA
http://dspace-roma3.caspur.it:80
The DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.2014-07-30T23:18:16ZSmall Screens and Large Graphs: Area-Effcient Drawings of Planar Combinatorial Structures
http://hdl.handle.net/2307/503
<Title>Small Screens and Large Graphs: Area-Effcient Drawings of Planar Combinatorial Structures</Title>
<Authors>Frati, Fabrizio</Authors>
<Issue Date>2009-04-02</Issue Date>
<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</Abstract>2009-04-01T22:00:00Z