ArcAdiA
http://dspace-roma3.caspur.it:80
The DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.2014-07-23T05:45:51ZOn the existence and optimality of some planar graph embeddings
http://hdl.handle.net/2307/650
<Title>On the existence and optimality of some planar graph embeddings</Title>
<Authors>Angelini, Patrizio</Authors>
<Issue Date>2010-03-30</Issue Date>
<Abstract>A graph is an abstract mathematical representation of a set of objects, called vertices, together
with a pairwise relationship between such objects, that is represented by a collection of edges
connecting pairs of vertices. Examples of relationships among objects that are representable by a
graph can be found in every ﬁeld, ranging from interpersonal relationships to computer networks
and from knowledge representation to bioinformatics. Of course, the best way to make such a
relationship clearly understandable is to visualize the graph so that vertices and edges are easily
recognizable at human eye. Such an issue is addressed in the research ﬁeld of Graph Drawing,
which can be regarded as a cross between the areas of Graph Theory, Graph Algorithmic, and
Computational Geometry.
In Graph Drawing, the most common way to visualize a graph is to draw each vertex as a point
in the plane and each edge as a curve connecting the corresponding points. The placement of the
vertices in the plane and the drawing of the curves should be performed in such a way that the
resulting drawing be nice and readable, in the sense that the information described by the graph
should be possibly understandable at a glance. In order to obtain the desired nice and readable
visualization, it is important to formalize the aesthetic criteria that distinguish a “good” drawing
from a “bad” one. Then, the goal of Graph Drawing is to create algorithms that automatically
produce drawings respecting such criteria.
The most natural aesthetic criterion that one can think of is probably the absence of partial
or complete overlapping among vertices and edges, that is called planarity. Another important
criterion that one has to consider when drawing a graph is the area of the drawing, as a drawing
with a small area can be better visualized inside a small screen. Observe that, while planarity is a
property that a drawing may satisfy or not, the drawing area is a measure of quality that can be used
to compare two drawings. Many other properties and quality measures can be deﬁned concerning
the visualization of graphs, even with the possibility of combining some of them. However, the
“best” drawing of a graph might not exist, since drawings that are “good” in terms of a certain
criterium may be “bad” in terms of another.
It is interesting to observe that some of the aesthetic criteria of a drawing of a graph only
depend on its topological features, while other criteria also depend on the geometrical realization.
For example, an important theorem in Graph Drawing, known as Fary’s Theorem, states that every
graph admitting a planar drawing also admits a planar drawing in which edges are represented by
straight-line segments. This implies that, in order to decide whether a given graph admits a planar
drawing, it is possible to study whether such a graph admits a planar embedding, that is, a circular
ordering of the edges around each vertex that determines no topological crossing in the induced
drawing, rather than computing the actual coordinates of the points representing the vertices. On
the other hand, given a graph with a ﬁxed embedding, diﬀerent geometrical realizations may lead
to drawings with diﬀerent area.
Several natural and interesting to study questions can be formulated concerning the aesthetic
criteria deﬁned for the graphical representation of graphs.
When considering a graph property, the ﬁrst, and probably most natural, arising question is
the one about the existence of graphs satisfying such a property and of graphs not satisfying it. If
both positive and negative instances exist, the problem can then be studied by either asking for
a characterization of the family of graphs that satisfy the desired property, or by determining the
computational complexity of the problem of deciding whether a given graph satisﬁes the property.
On the other hand, when considering a particular measure of quality of a drawing or of an
embedding, the two most natural questions are certainly the one asking for the optimal value of
such a measure among all the graphs of a certain family and the one asking for an eﬃcient algorithm
that optimizes such a measure for a given graph.
In this thesis we address and partially answer such questions on several classes and types
of graphs, as we propose algorithms for computing planar embeddings or drawings that satisfy
certain properties or that are optimal with respect to certain measures of quality. We mainly
deal with planar graphs and with graph properties and measures that depend on the topology
of the graph (Part II) and on its geometry (Part III). Also, we consider the same questions on
simultaneous graph drawing problems (Part IV), that is, problems involving more than one graph,
and on clustered graphs (Part V), that is, graphs where the vertices are grouped into clusters by
means of a hierarchical structure.</Abstract>2010-03-29T22:00:00Z