A method for computationally efficient skeletonization of three-dimensional tubular structures is reported. The method is specifically targeting skeletonization of vascular and airway tree structures in medical images but it is general and applicable to many other skeletonization tasks. The developed approach builds on the following novel concepts and properties: fast curve-thinning algorithm to increase computational speed, endpoint re-checking to avoid generation of spurious side branches, depth-and-length sensitive pruning, and exact tree-branch partitioning allowing branch volume and surface measurements. The method was validated in computer and physical phantoms and in vivo CT scans of human lungs. The validation studies demonstrated sub-voxel accuracy of branch point positioning, insensitivity to changes of object orientation, and high reproducibility of derived quantitative indices of the tubular structures offering a significant improvement over previously reported methods (p<<0.001).