  We study the classic problem of fairly dividing a heterogeneous and divisible
resource -- represented by a cake, $[0,1]$ -- among $n$ agents. This work
considers an interesting variant of the problem where agents are embedded on a
graph. The graphical constraint entails that each agent evaluates her allocated
share only against her neighbor's share. Given a graph, the goal is to
efficiently find a locally envy-free allocation where every agent values her
share to be at least as much as any of her neighbor's share.
  The best known algorithm (by Aziz and Mackenzie) for finding envy-free cake
divisions has a hyper-exponential query complexity. One of the key technical
contributions of this work is to identify a non-trivial graph structure -- tree
graphs with depth at-most two (Depth2Tree) -- on $n$ agents that admits a query
efficient cake-cutting protocol (under the Robertson-Webb query model). In
particular, we develop a discrete protocol that finds a locally envy-free
allocation among $n$ agents on depth-two trees with at-most $O(n^3 \log(n))$
cuts on the cake. For the special case of Depth2Tree where every non-root agent
is connected to at-most two agents (2-Star), we show that $O(n^2)$ queries
suffice. We complement our algorithmic results with establishing a lower bound
of $\Omega(n^2)$ (evaluation) queries for finding a locally envy-free
allocation among $n$ agents on a 1-Star graph (under the assumption that the
root agent partitions the cake into $n$ connected pieces).
