As a remarkable difference to the existing CAD technology, where shapes are represented by their boundaries, FEM-based isogeometric analysis typically needs a parameterization of the interior of the domain. Due to the strong influence on the accuracy of the analysis, methods for constructing a good parameterization are fundamentally important. The flexibility of single patch representations is often insufficient, especially when more complex geometric shapes have to be represented. Using a multi-patch structure may help to overcome this challenge. In this paper we present a systematic method for exploring the different possible parameterizations of a planar domain by collections of quadrilateral patches. Given a domain, which is represented by a certain number of boundary curves, our aim is to find the optimal multi-patch parameterization with respect to an objective function that captures the parameterization quality. The optimization considers both the location of the control points and the layout of the multi-patch structure. The latter information is captured by pre-computed catalogs of all available multi-patch topologies. Several numerical examples demonstrate the performance of the method. •A method for finding a multi-patch parameterization for a domain is presented.•The control points as well as the layout of the multi-patch structure are considered.•Pre-computed catalogs of all available multi-patch topologies are used.