Textline detection in natural images has been an important problem and researchers have attempted to address this problem by grouping connected components (CCs) into clusters corresponding to textlines. However, developing bottom-up rules that work for multiorientation and/or multiscript textlines is not a simple task. In order to address this problem, we propose a framework that incorporates projection profile analysis (PPA) into the CC-based approach. Specifically, we build a graph of CCs and recursively partition the graph into subgraphs, until textline structures are detected by PPA. Although PPA has been a common technique in document image processing, it was developed for scanned documents, and we also propose a method to compute projection profiles for CCs. Experimental results show that our method is efficient and achieves better or comparable performance on conventional datasets (ICDAR 2011/2013 and MSRA-TD500), and shows promising results on a challenging dataset (ICDAR 2015 incidental text localization dataset).