Ares Ribó Mor

Realization and Counting Problems for Planar Structures: Trees and Linkages, Polytopes and Polyominoes

Betreuer: Prof. Dr. Günter Rote
Abschluss: PhD
Abgabedatum: 15.02.2006
Homepage des Autors:


Part I of my thesis is about planar linkages. We consider motions of linkages that avoid crossings of bars. We study problems related to self-touching frameworks, in which multiple edges converge to geometrically overlapping configurations. Chapter 2 is about the unfoldability of trees. We show that every monotone tree is unfoldable. A δ-perturbation of a self-touching configuration is a repositioning of the vertices within disks of radius δ, which is consistent with the combinatorial embedding in R2. In Chapter 3 we prove that every self-touching configuration can be perturbed within δ. The classical Maxwell-Cremona Theorem is a powerful tool that establishes a bijection between the set of classical equilibrium stresses of a planar configuration and the set of three-dimensional polyhedral terrains that project onto it. In Chapter 4 we present a generalization of the Maxwell-Cremona Correspondence for self-touching configurations and generalized polyhedral terrains.

Part II is about the number of spanning trees of a planar graph with applications to the embedding of polytopes on small integer grids using the Maxwell-Cremona lifting. In Chapter 5 we give lower and upper bounds for the maximum number of spanning trees. We present a new method based on transfer matrices for computing the asymptotic number of spanning trees of recursively constructible families of graphs. We discuss several techniques for obtaining upper bounds. Apart from the general case, we study the particular cases when the graph has smallest face cycle 4 and 5, for which the best results are obtained using a probabilistic method. These results are used in Chapter 6 for obtaining improved bounds on the minimum size of the integral grid in which all combinatorial types of 3-polytopes can be embedded.

In Part III we analyze, using numerical methods, the growth in the number of polyominoes on a twisted cylinder as the number of cells increases. These polyominoes are related to classical polyominoes (connected subsets of a square grid) that lie in the plane. We thus obtain improved lower bounds on the growth rate of the number of these polyominoes, which is also known as Klarner's constant.