Extended Depth-First Representations of $k^2$-trees

This paper addresses the problem of poor cache performance and memory locality in traditional level-wise $k^2$-tree layouts for static graph compression. The authors propose four depth-first representations—EDF-1, BP, CEDF, and CBP—along with a linear-time compression method using suffix and LCP arrays to merge identical subtrees. Experiments on Web Graphs, Wikidata, and random adjacency matrices show that CEDF achieves the best compression in most cases, EDF-1 and CEDF consistently reduce peak memory usage, and performance varies by workload across matrix-vector and matrix-matrix operations. These findings establish depth-first $k^2$-tree layouts as a practical, efficient alternative to traditional layouts, improving both compression and computational performance in linear-algebra operations.