Finding twin vertices in graphs
Twins in a graph are just modules of size 2. The modular decomposition of a graph can be found in $O(n+m)$ time. The modular decomposition tree implicitly represents all modules of the graph and consists of three types of internal nodes: series, parallel and prime nodes, and the leaves consists of the individual nodes. A set of at least two vertices $S \subset V$ is a module if and only if it is some node in the tree or the union of some set of children of a series or a parallel node.

So to find a pair of twin nodes, if they exist, we can construct the modular decomposition tree in $O(n+m)$ time. Then look at the leaves, if the parent of any leaf is a series or parallel node then that node must have at least two children which form a twin pair. So the total running time is linear.

http://en.wikipedia.org/wiki/Modular_decomposition