Planar Cycle Covering Graphs

Julian Yarkony, Alexander T. Ihler, Charless C. Fowlkes

We describe a new variational lower-bound on the minimum energy configuration of a planar binary Markov Random Field (MRF). Our method is based on adding auxiliary nodes to every f…