  We study the problem of fairly allocating a divisible resource in the form of
a graph, also known as graphical cake cutting. Unlike for the canonical
interval cake, a connected envy-free allocation is not guaranteed to exist for
a graphical cake. We focus on the existence and computation of connected
allocations with low envy. For general graphs, we show that there is always a
$1/2$-additive-envy-free allocation and, if the agents' valuations are
identical, a $(2+\epsilon)$-multiplicative-envy-free allocation for any
$\epsilon > 0$. In the case of star graphs, we obtain a multiplicative factor
of $3+\epsilon$ for arbitrary valuations and $2$ for identical valuations. We
also derive guarantees when each agent can receive more than one connected
piece. All of our results come with efficient algorithms for computing the
respective allocations.
