Luis Goddyn

Department of Mathematics
Faculty of Science

Areas of interest

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 description. 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 research 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.


  • Ph.D. Mathematics · University of Waterloo · 1989

Research Areas


Future courses may be subject to change.