In this work, we extend a novel seed-based segmentation algorithm, which provides global optimum solutions according to a graph-cut measure, subject to high-level boundary constraints: The simultaneously handling of boundary polarity and connectivity constraints. The proposed method incorporates the connectivity constraint in the Oriented Image Foresting Transform (OIFT), ensuring the generation of connected objects, but such that the connection between its internal seeds is guaranteed to have a user-controllable minimum width. In other frameworks, such as the min-cut/max-flow algorithm, the connectivity constraint is known to lead to NP-hard problems. In contrast, our method conserves the low complexity of the OIFT algorithm. In the experiments, we show improved results for the segmentation of thin and elongated objects, for the same amount of user interaction. Our dataset of natural images with true segmentation is publicly available to the community.