Graph-theoretical methods in object recognition and related problems in extremal graph theory

A key problem in computer vision is how to represent an image in terms for coding such features and their spatial relations, but offer a framework for object indexing and recognition. In this thesis, we will present applications of graph theoretical methods to specific problems in object recognition. In one instance, we develop two novel coarse-to-fine bipartite matching algorithms to match hierarchical image descriptions based on salient image regions. The first algorithm compares the topological structure of two directed acyclic graphs, while the second algorithm adds geometric information encoded in the graphs. In a related problem, we develop indexing and matching methods for the domain of 2-D silhouette recognition. Given a shock tree representation of a closed curve, we develop a novel topological description of a tree based on a spectral characterization of its branching structure. This compact topological signature is exploited in a novel indexing algorithm, and forms the heart of a novel bipartite matching algorithm for computing the distance and correspondence between two shock trees.; In the second part of the thesis, we explore some related problems in extremal graph theory. First, we will prove an embedding conjecture for graphs with maximum degree 3 due to Bollóbas and Eldridge. The original conjecture states that if G is an n -vertex graph with minimum degree at least (k/( k + 1))n, then G contains any n-vertex graph having maximum degree at most k. We prove this conjecture for k = 3. The second result is the proof of a tiling conjecture due to Komlós. For graphs G and H, an H-matching in G is a subgraph of G consisting of vertex-disjoint copies of H. For an r-chromatic graph H on h vertices, we write σ = σ( H) for the smallest possible color-class size in any r-coloring of H. The critical chromatic number of H is the number χ_cr(H) = ( r − 1)h/(h − σ). Komlós conjectured that for every graph H there is a constant K such that, if G is an n-vertex graph of minimum degree at least (1 − (1/χ _cr(H)))n, then G contains an H-matching that covers all but at most K vertices. We prove this conjecture for all sufficiently large values of n.