Automatic labeling of the gyri and sulci on the cortical surface is important for studying cortical morphology and brain functions within populations. A method to simultaneously label gyral regions and extract sulcal curves is proposed. Assuming that the gyral regions parcellate the whole cortical surface into contiguous regions with certain fixed topology, the proposed method labels the subject cortical surface by deformably registering a network of curves that form the boundary of gyral regions to the subject cortical surface. In the registration process, the curves are encouraged to follow the fine details of the sulcal geometry and to observe the shape statistics learned from training data. Using the framework of probabilistic point set registration methods, the proposed algorithm finds the sulcal curve network that maximizes the posterior probability by Expectation-Maximization (EM). The automatic labeling method was evaluated on 15 cortical surfaces using a leave-one-out strategy. Quantitative error analysis is carried out on both labeled regions and major sulcal curves.