Our main result is an O(nm)-time (deterministic) algorithm for constructing an ear decomposition of a matching-covered graph, where n and m denote the number of nodes and edges. The improvement in the running time comes from new structural results that give a sharpened version of Lovász and Plummer's Two-Ear Theorem. Our algorithm is based on O(nm)-time algorithms for two other fundamental problems in matching theory, namely, finding all the allowed edges of a graph, and finding the canonical partition of an elementary graph. To the best of our knowledge, no faster deterministic algorithms are known for these two fundamental problems.