Succinct Data Structures for Bounded Degree/Chromatic Number Interval Graphs

An interval graph is the intersection graph of intervals on the real line. We consider the problem of constructing space efficient data structures for two subclasses of interval graphs: those with maximum degree σ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> and those with chromatic number at most σ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> .We show that both bounded degree and bounded chromatic number interval graphs have a tight lower bound of n lg σ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf> − o(n lg σ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf> ) bits (i = 1, 2). This improves the lower bound of Chakraborty and Jo from 1/6n σ ᵢ - O(n). For bounded chromatic number interval graphs, we give the first succinct data structure occupying n lg σ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> + O(n) bits that supports navigational operations and distance queries in O(σ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> lgn) time. To match Chakraborty and Jo's time complexity of O(lg lg σ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> ), which uses (σ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> − 1)n+O(n) bits, we use 2nlgσ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> +O(n) bits instead.