PhD Mathematics · University of Waterloo · 1989
office SC K10523
My research falls into three areas, circuit structure of graphs and matroids, optimized Gray codes and Euclidean optimization problems.
The first of these areas is of current interest as there are close connections between circuit covers, matchings, flow theory, graph embeddings and the celebrated work of Seymour and Roberson on graph minors. In a recent paper with B. Alspach and C-Q Zhang we have found a forbidden-minor characterization of those graphs whose family circuit covers has a natural discription. This work singles out Petersen's graph as being exceptional, and lends support to Tutte's well known 4-flow conjecture. I have now extended this work to the class of binary matroids, and also to the problem of Matching Covers.
The second area of reasearch is related to a new type of optimization problem involving Gray codes. Gray codes are commonly used in the design of position-digital converters and communication codes. This particular research was motivated by a digital space telescope application at LASP, Colorado. The performance of this telescope was greatly improved by using a specialized Gray code in its design. Constructing such specialized Gray codes (and their abstractions) is an on-going project which involves computer searches and direct constructions.
The third area involves the well-known Euclidean Traveling Salesman Problem. I have improved some bounds in the worst-case analysis of this problem by estimating the performance of certain heuristics based on quantizers. Quantizers are used in information theory and communication as a way of digitizing blocks of information.