Center and diameter problems in plane triangulations and quadrangulations
Victor D. Chepoi, Feodor F. Dragan, Yann Vaxès · 2002
In this note, we present first linear time algorithms for computing the center and the diameter of several classes of face regular plane graphs: triangulations with inner vertices of degree >= 6, quadrangulations with inner vertices of degree >= 4 and the subgraphs of the regular hexagonal grid bounded by a simple circuit of this grid.