Logo image
Back
Succinct navigational oracles for families of intersection graphs on a circle
Journal article   Open access   Peer reviewed

Succinct navigational oracles for families of intersection graphs on a circle

Hüseyin Acan, Sankardeep Chakraborty, Seungbum Jo, Kei Nakashima, Kunihiko Sadakane and Srinivasa Rao Satti
Theoretical computer science, v 928
03 Sep 2022
DOI: https://doi.org/10.1016/j.tcs.2022.06.022
url
http://arxiv.org/abs/2010.04333View
SubmittedOpen Access (License Unspecified),  Open

Abstract

Intersection graph Navigational query Succinct data structure
We consider the problem of designing succinct navigational oracles, i.e., succinct data structures supporting basic navigational queries such as degree, adjacency and neighborhood efficiently for intersection graphs on a circle, which include graph classes such as circle graphs, k-polygon-circle graphs, circle-trapezoid graphs, trapezoid graphs. The degree query reports the number of incident edges to a given vertex, the adjacency query asks if there is an edge between two given vertices, and the neighborhood query enumerates all the neighbors of a given vertex. We first prove a general lower bound for these intersection graph classes, and then present a uniform approach that lets us obtain matching lower and upper bounds for representing each of these graph classes. More specifically, our lower bound proofs use a unified technique to produce tight bounds for all these classes, and this is followed by our data structures which are also obtained from a unified representation method to achieve succinctness for each class. In addition, we prove a lower bound of space for representing trapezoid graphs, and give a succinct navigational oracle for this class of graphs.

Metrics

10 Record Views
3 citations in Web of Science
5 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, Theory & Methods
Logo image