Computational searches for new materials are naturally turning from binary systems, to ternary and other multicomponent systems, and beyond. Here, we select the industrially-relevant metals Ti and Al and report the results of an extensive structure prediction study on the ternary titanium-carbon-oxygen (Ti-C-O) and aluminium-carbon-oxygen (Al-C-O) systems. We map out for the first time the full phase stability of Ti-C-O and Al-C-O compounds using first-principles calculations, through simple, effcient and highly parallel random structure searching in conjunction with techniques based on complex network theory. This record contains the crystal structures used to generate our ternary convex hulls for these systems. We provide input files for the CASTEP density-functional theory code, crystallographic '.res' files of the relaxed structures, and CASTEP output files showing atomic positions and forces calculated during relaxation.