(data structure)

**Definition:**
A *compact* representation of a sparse *directed graph*. It requires 1 to 3 *bits* per edge. Many access functions, like successor(s), predecessor(s), and range (all links from a range of *vertices* to another range of vertices), have very efficient implementations.

**Generalization** (I am a kind of ...)

*compact data structure*.

**Aggregate child** (... is a part of or used in me.)

*adjacency-matrix representation*, *quadtree*.

*Note:
A k²-tree is particularly useful for Web graphs, which are very sparse. This needs (N + o(N))/N bits per edge, where N is the number of edges. Checking if there is an edge from any vertex to another takes O(log_{k} N), where k is the branching factor.*

Author: PEB

**Nieves R. Brisaboa**, **Susana Ladra**, and **Gonzalo Navarro**, *Compact representation of Web graphs with extended functionality*, Information Systems vol 39, pages 152-174, 2014. doi 10.1016/j.is.2013.08.003

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 8 June 2023.

HTML page formatted Thu Jun 8 11:24:36 2023.

Cite this as:

Paul E. Black, "k²-tree", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 8 June 2023. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/k2tree.html