  The three-in-a-tree problem is to determine if a simple undirected graph
contains an induced subgraph which is a tree connecting three given vertices.
Based on a beautiful characterization that is proved in more than twenty pages,
Chudnovsky and Seymour [Combinatorica 2010] gave the previously only known
polynomial-time algorithm, running in $O(mn^2)$ time, to solve the
three-in-a-tree problem on an $n$-vertex $m$-edge graph. Their three-in-a-tree
algorithm has become a critical subroutine in several state-of-the-art graph
recognition and detection algorithms.
  In this paper we solve the three-in-a-tree problem in $\tilde{O}(m)$ time,
leading to improved algorithms for recognizing perfect graphs and detecting
thetas, pyramids, beetles, and odd and even holes. Our result is based on a new
and more constructive characterization than that of Chudnovsky and Seymour. Our
new characterization is stronger than the original, and our proof implies a new
simpler proof for the original characterization. The improved characterization
gains the first factor $n$ in speed. The remaining improvement is based on
dynamic graph algorithms.
