Michael Dillencourt
A recent SODA paper by Chepoi, Dragan and Vaxes [CDV] presented linear-time algorithms for computing the diameter and center in several classes of face-regular planar graphs. Among these classes of graphs are trigraphs (triangulations in which inner vertices have degree >= 6), triangular systems (triangulations in which inner vertices have degree = 6), and hexagonal systems (subgraphs of a regular hexagonal grid, bounded by a simple circuit). In this talk, I will discuss some of their results, focusing on the problem of computing the diameter.
Full citation of [CDV]: Victor Chepoi, Feodor Dragan, and Yann Vax\`es, Center and Diameter problems in plane triangulations and quadrangulations, Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), San Francisco, CA, January 2002, 346-355.