In this paper we propose an automated approach for joint sulci detection on cortical surfaces by using graphical models and boosting techniques to incorporate shape priors of major sulci and their Markovian relations. For each sulcus, we represent it as a node in the graphical model and associate it with a sample space of candidate curves, which is generated automatically using the Hamilton-Jacobi skeleton of sulcal regions. To take into account individual as well as joint priors about the shape of major sulci, we learn the potential functions of the graphical model using AdaBoost algorithm to select and fuse information from a large set of features. This discriminative approach is especially powerful in capturing the neighboring relations between sulcal lines, which are otherwise hard to be captured by generative models. Using belief propagation, efficient inferencing is then performed on the graphical model to estimate each sulcus as the maximizer of its final belief. On a data set of 40 cortical surfaces, we demonstrate the advantage of joint detection on four major sulci: central, precentral, postcentral and the sylvian fissure.