# ICS 269, Winter 2002: Theory Seminar

## 15 March 2002:

A presentation of results from
"Center and diameter problems
in plane triangulations and quadrangulations,"
by Victor Chepoi, Feodor Dragan, and Yann Vaxes

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.