Complexity of diameter on AT-free graphs is linear

We develop a linear time algorithm for finding the diameter of an AT-free graph. Furthermore, we update the definition of polar sets and develop new properties of polar sets for (weak) dominating pair graphs. We prove that the problems of finding simplicial vertices and finding triangles in general graphs can be accomplished in O(n^2) based on existing reductions of these problems to the problem of finding diameter in AT-free graphs. We improve the best-known run-time complexities of several graph theoretical problems.