  Probabilistic graphical models (PGMs) are tools for solving complex
probabilistic relationships. However, suboptimal PGM structures are primarily
used in practice. This dissertation presents three contributions to the PGM
literature. The first is a comparison between factor graphs and cluster graphs
on graph colouring problems such as Sudokus - indicating a significant
advantage for preferring cluster graphs. The second is an application of
cluster graphs to a practical problem in cartography: land cover classification
boosting. The third is a PGMs formulation for constraint satisfaction problems
and an algorithm called purge-and-merge to solve such problems too complex for
traditional PGMs.
