In the general Graph Label Placement (GLP) problem, the goal is to assign coordinate positions to labels for various graph elements, typically nodes and edges (In cartographic applications, it is also common to label regions in the layout). While a seemingly simple task, this problem has been proven to be computationally NP-complete. This means that it is computationally difficult to find an optimal labeling solution to a general graph. In the Node Label Placement (NLP) problem, the goal is to assign coordinate positions to the nodes of a graph. In the Edge Label Placement (ELP) problem, the goal is to assign coordinate positions to the edges of a graph. In each of these problems, similar constraints exist: labels should unambiguously refer to the graph elements they label and overlaps with other graph elements and labels should be avoided as much as is possible. There are several types of approach that have been used to solve the graph labeling problem. The most common approach has been to use an optimization approximation algorithm such as simulated annealing to optimize a cost function of the label assignment. How the costs are determined and the specific method of optimization used differs depending on the solution and the problem at hand. Another approach is to map the label assignment to another (usually graph theoretic) problem and attempt to solve that problem. In all of these cases, the label assignment is very computationally intensive, and can be even more difficult to compute depending on the type of graph drawing used, for example, if edges contain bends. The problem is further complicated by the fact that many graph layouts may yield no complete labeling solution-that is, no labeling may be possible that labels all graph features unambiguously and without overlap. One approach to decrease this problem and to address the labeling problem is to incorporate the space required for the labels in the graph layout process itself rather than the more common approach of using a fixed graph layout and assigning label positions to the graph features in that layout. This approach stems from the fact that graph labeling is most frequently applied to automated cartography, where it is very difficult to relocate the graph features (e.g. cities, rivers, etc.). Even with this insight, however, the problem remains extremely difficult-the graph layout problem and the graph labeling problem alone are difficult enough without the additional constraint that the layout must support an optimal labeling.