Graph labeling scheme reduces extra bits for bounded treewidth graphs
Adjacency Labeling Schemes of Size $\log n+O(\log\log^* n)$ for Graphs of Bounded Treewidth
Data Structures and AlgorithmsDiscrete Mathematics
Summary
Some networks can be represented as special types of graphs called bounded treewidth graphs. Gavoille and Labourel previously showed how to label these graphs so you can quickly check if two points are connected, but their method still used quite a few extra bits. The authors improve on this by reducing the extra information needed to almost just a constant amount beyond the basic size needed to identify points. They achieve this by cleverly rearranging parts of the graph and using a more complex labeling method. This means we can represent these graphs more efficiently and still quickly check connections.
What this means in practice
- •For network algorithm engineers: Construct compact labels enabling efficient neighbor queries on bounded treewidth network topologies with lower storage overhead.
- •For data structure developers: Design more space-efficient data structures for representing graphs whose complexity is limited by treewidth.
A theory result. No direct application yet.
Authors
Noy Rotbart
Abstract
Gavoille and Labourel (ESA 2007) gave an adjacency labeling scheme of size $\log n+O(k\log\log n)$ for graphs of treewidth at most $k$, and asked whether $\log n+O(k)$ bits suffice. We give a labeling scheme of size $\log n+O(\log\log^* n)$ for every fixed $k$, the first improvement of the second-order term for any $k\ge 2$. Equivalently, there is an induced-universal graph with $n(\log^* n)^{O_k(1)}$ vertices for this family. We work with laminar families of intervals, in which a vertex finds each earlier neighbor as the owner of an interval of a given nesting depth around it. As long as every subtree occupies consecutive positions, the nesting depth must be logarithmic, and $\log\log n$ bits per neighbor follow. We give up contiguity. Heavy subtrees are moved out, which brings the depth down to $O(\log^* n)$; the intervals broken by the moves are repaired with $2^{O(k^3)}$ additional intervals per vertex; and the bits needed to find these intervals are paid for by the moved subtrees.