Sorry, you need to enable JavaScript to visit this website.

Compact Representation of Graphs with Small Bandwidth and Treedepth

Citation Author(s):
Submitted by:
Shahin Kamali
Last updated:
22 April 2020 - 1:50pm
Document Type:
Document Year:
Shahin Kamali
Paper Code:
204 (session 8)

We consider the problem of compact representation of graphs with small bandwidth as well as graphs with small treedepth. These parameters capture structural properties of graphs that come in useful in certain applications.
We present simple navigation oracles that support degree and adjacency queries in constant time and neighborhood query in constant time per neighbor. For graphs of bandwidth $k$, our oracle takes $(k+ \lceil \log 2k\rceil)n +o(kn$) bits. By way of an enumeration technique, we show that $(k-5\sqrt{k}-4)n-O(k^{2})$ bits are required to encode a graph of bandwidth $k$ and size $n$. For graphs of treedepth $k$, our oracle takes $(k+\lceil\log k \rceil +2)n + o(kn)$ bits. We present a lower bound that certifies our oracle is succinct for certain values of $k \in o(n)$.

0 users have voted: