  We present a framework for designing differentially private (DP) mechanisms
for binary functions via a graph representation of datasets. Datasets are nodes
in the graph and any two neighboring datasets are connected by an edge. The
true binary function we want to approximate assigns a value (or true color) to
a dataset. Randomized DP mechanisms are then equivalent to randomized colorings
of the graph. A key notion we use is that of the boundary of the graph. Any two
neighboring datasets assigned a different true color belong to the boundary.
  Under this framework, we show that fixing the mechanism behavior at the
boundary induces a unique optimal mechanism. Moreover, if the mechanism is to
have a homogeneous behavior at the boundary, we present a closed expression for
the optimal mechanism, which is obtained by means of a \emph{pullback}
operation on the optimal mechanism of a line graph. For balanced mechanisms,
not favoring one binary value over another, the optimal $(\epsilon,\delta)$-DP
mechanism takes a particularly simple form, depending only on the minimum
distance to the boundary, on $\epsilon$, and on $\delta$.
