  We study the recently introduced cake-cutting setting in which the cake is
represented by an undirected graph. This generalizes the canonical interval
cake and allows for modeling the division of road networks. We show that when
the graph is a forest, an allocation satisfying the well-known criterion of
maximin share fairness always exists. Our result holds even when separation
constraints are imposed, in which case no multiplicative approximation of
proportionality can be guaranteed. Furthermore, while maximin share fairness is
not always achievable for general graphs, we prove that ordinal relaxations can
be attained.
