Logo image
Back
Succinct Data Structures for Families of Interval Graphs
Conference proceeding   Open access   Peer reviewed

Succinct Data Structures for Families of Interval Graphs

Huseyin Acan, Sankardeep Chakraborty, Seungbum Jo and Srinivasa Rao Satti
ALGORITHMS AND DATA STRUCTURES, WADS 2019, v 11646
01 Jan 2019
DOI: https://doi.org/10.1007/978-3-030-24766-9_1
url
http://arxiv.org/abs/1902.09228View
SubmittedOpen Access (License Unspecified),  Open

Abstract

Computer Science Computer Science, Software Engineering Computer Science, Theory & Methods Mathematics Mathematics, Applied Physical Sciences Science & Technology Technology
We consider the problem of designing succinct data structures for interval graphs with n vertices while supporting degree, adjacency, neighborhood and shortest path queries in optimal time. Towards showing succinctness, we first show that at least n log(2) n-2n log(2) log(2) n-O(n) bits. are necessary to represent any unlabeled interval graph G with n vertices, answering an open problem of Yang and Pippenger [Proc. Amer. Math. Soc. 2017]. This is augmented by a data structure of size n log(2) n + O(n) bits while supporting not only the above queries optimally but also capable of executing various combinatorial algorithms (like proper coloring, maximum independent set etc.) on interval graphs efficiently. Finally, we extend our ideas to other variants of interval graphs, for example, proper/unit, k-improper interval graphs, and circular-arc graphs, and design succinct data structures for these graph classes as well along with supporting queries on them efficiently.

Metrics

6 Record Views
12 citations in Web of Science
7 citations in Scopus

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Collaboration types
Domestic collaboration
International collaboration
Web of Science research areas
Computer Science, Software Engineering
Computer Science, Theory & Methods
Mathematics, Applied
Logo image