In this thesis, we investigate the contraction reconstruction conjecture. It states that all simple graphs with at least four edges are reconstructible, that is they are uniquely determined from their collection of single edge contraction minors, called the deck. Similar questions have been studied in the past, the vertex reconstruction conjecture being the most famous. There are usually two steps to show that a class of graph is reconstructible. The first one is to show that the class is recognizable, meaning that it is possible to determine if a graph G belongs to that class by looking at its deck. In order to recognize some classes of graphs, we show that a wide range of graph properties are reconstructible. We investigate the connectivity of graphs, which is useful to recognize disconnected, separable, and 2-connected graphs. We also show that the number of cycles of various lengths, the degree sequence, the number of spanning trees, the planarity, the presence of cliques of various sizes, and the diameter are reconstructible. Knowing the lengths of cycles allows us to recognize the class of bipartite graphs, while knowing the degree sequence allows us to recognize regular graphs. The second step in showing that a class of graph is reconstructible is called weak reconstruction. We say that a class of graph is weakly reconstructible if no two graphs in that class share the same deck. A class of graphs that is both weakly reconstructible and recognizable is reconstructible. In this thesis, we show that disconnected graphs, bipartite graphs, most separable graphs and most 2-edge connected graphs are reconstructible. We also show that distance regular graphs and some cubic graphs are reconstructible. We quickly delve into the theory of probabilities to give a proof that almost all graphs are reconstructible. Finally, the relation between edge contraction and graph automorphisms is studied. We study the automorphism group of a graph in relation to those of its cards. We also study the concept of contraction pseudo-similarity. Two edges are contraction pseudo-similar if they are not similar, but their contractions yield isomorphic graphs. We completely characterize the graphs that contain contraction pseudo-similar edges.

No description available.

Many applications in computer graphics and related fields can benefit fromautomatic simplification of complex polygonal surface models. Applications areoften confronted with either very densely over-sampled surfaces or models toocomplex for the limited available hardware capacity. An effective algorithmfor rapidly producing high-quality approximations of the original model is avaluable tool for managing data complexity. In this dissertation, I present my simplification algorithm, based on iterativevertex pair contraction. This technique provides an effective compromisebetween the fastest algorithms, which often produce poor quality results, andthe highest-quality algorithms, which are generally very slow. For example, a1000 face approximation of a 100,000 face model can be produced in about 10seconds on a PentiumPro 200. The algorithm can simplify both the geometryand topology of manifold as well as non-manifold surfaces. In addition toproducing single approximations, my algorithm can also be used to generatemultiresolution representations such as progressive meshes and vertex hierarchiesfor view-dependent refinement. The foundation of my simplification algorithm, is the quadric error metricwhich I have developed. It provides a useful and economical characterization oflocal surface shape, and I have proven a direct mathematical connection betweenthe quadric metric and surface curvature. A generalized form of this metric canaccommodate surfaces with material properties, such as RGB color or texturecoordinates. I have also developed a closely related technique for constructing a hierarchyof well-defined surface regions composed of disjoint sets of faces. This algorithminvolves applying a dual form of my simplification algorithm to the dual graphof the input surface. The resulting structure is a hierarchy of face clusters whichis an effective multiresolution representation for applications such as radiosity.