In this paper, we introduce a novel star partitioning problem for simple connected graphs \(G=(V,E)\) . The goal is to find a partition of the edges into stars that minimizes the maximum number of stars a node is contained in while simultaneously satisfying node-specific capacities. We design and analyze an efficient polynomial time algorithm with a runtime of \(\mathcal {O}(|E|^2)\) that determines an optimal partition. Moreover, we explicitly provide a closed form of an optimal value for some graph classes. We generalize our algorithm to find even an optimal star partition of linear hypergraphs, multigraphs, and graphs with self-loops. We use flow techniques to design an algorithm for the star partitioning problem with an improved runtime of \(\mathcal {O}(\log (\varDelta ) \cdot |E| \cdot \min \{|V|^{\frac{2}{3}},|E|^{\frac{1}{2}}\})\) , where \(\varDelta \) is maximum node degree in G. In contrast to the unweighted setting, we show that a node-weighted decision variant of this problem is strongly NP-complete even without capacity constraints. Furthermore, we provide an extensive comparison to the problem of minimizing the minimum indegree satisfying node capacity constraints.