| Title | : | On Succinct Data Structures for Certain Generalisations of Interval Graphs |
| Speaker | : | Girish Balakrishnan (IITM) |
| Details | : | Thu, 4 Jul, 2024 11:00 AM @ ALC Hall (SSB 223) |
| Abstract: | : | In this work, we explore generalizations of interval graphs based on three different graph parameters,
namely, boxicity d > 0, interval number t > 0, and vertex leafage k > 0 by designing succinct data structures for
them. A data structure for graphs in the class of graphs mathcal{G} is called succinct if it takes
log |mathcal{G}| + o(log |mathcal{G}|) bits of space. The graph parameters, boxicity, and interval number are
defined for general graphs, whereas the graph parameters vertex leafage and leafage are defined for chordal
graphs alone. These parameters let us define graph classes with a laminar structure with interval graphs as the
base class. Utilizing this laminar structure we design data structure for the class of graphs with larger values of
these parameters using the succinct data structure for the base class. For c > 0, a unit increase in any of the three
parameters adds only n^{cn} number of graphs. So such a data structure design technique gives a space-efficient
representation only when the parameters are bounded, since c depends on the parameters and the parameters can
be O(n). Further, we prove that under these conditions the representations are succinct. We show that, for graph
classes defined based on boxicity and interval number, the base class is interval graphs. However, for a succinct
data structure for the graph class based on vertex leafage, a base class with vertex leafage of two and unbounded
leafage is better suited than interval graphs that have both vertex leafage and leafage equal to two. It turns out that
such a class of graphs is well-studied and is called path graphs. We present the design of succinct data structures
for the following generalizations of interval graphs based on these three parameters: - path graphs, which is a strict super-class of interval graphs and a strict sub-class of chordal graphs, - graphs with bounded boxicity d > 0 and graphs with bounded interval number t > 0, and - chordal graphs with bounded vertex leafage k > 0 and unbounded leafage. The succinct data structures for graphs with bounded boxicity and interval number are obtained using the succinct data structure for interval graphs given by Acan et al. (LNTCS, volume 11646). In the case of chordal graphs with bounded vertex leafage, the succinct data structure is obtained using the succinct data structure for path graphs. The graph classes considered in this work are all factorial speed hereditary properties with simple structural characterizations that we obtain as part of our constructive lower bound argument for the cardinality of these graph classes. Our lower bound arguments, based on the partial coloring scheme introduced by Acan et al. (Theor. Comput. Sci. 2022) demonstrate that using this scheme we not only obtain the lower bound of the cardinality of the graph class under consideration but also its structural characterisation. As per Lozin 2018, the structural characterization of factorial speed hereditary properties is an open problem. We raise the question: Does boxicity structurally characterize the factorial speed hereditary property? We conclude that the answer is not immediately evident motivating further study. Web Conference Link : https://meet.google.com/wco-vqpu-zia |
