On the existence and optimality of some planar graph embeddings

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 field, 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 field 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 defined 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 fixed embedding, different geometrical realizations may lead to drawings with different area. Several natural and interesting to study questions can be formulated concerning the aesthetic criteria defined for the graphical representation of graphs. When considering a graph property, the first, 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 satisfies 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 efficient 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.