off topic: Regarding Figure 8: "a graph with 10 nodes, each having 4 neighbors and no two shards requiring more than 2 hops for cross-shard communication". This can be achieved with only 3 neighbors (Petersen graph) https://en.wikipedia.org/wiki/Petersen_graph