Placing numerous objects and their corresponding labels in the stacked graph visualization is a challenging problem. In the stacked graph, different combinations of initial parameters and filtering effects yield views with hidden information, illegible labels, and unused space. The result is a tool that does not take advantage on the unused space to reveal information to the user for further investigation. We present an automatic method for label layout on the unused space in a stacked graph. An evolutionary computation (EC) is used to optimize the best label position according to legibility requirements, as well as requirements for keeping semantic relationships between labels and their representative visual objects. A number of EC experiments, as well as a usability study on label legibility, show that our proposed solution looks promising, as compared to the traditional solutions.