Conference proceeding
Succinct representations of Intersection Graphs on a Circle
2021 Data Compression Conference (DCC), v 2021-, pp 123-132
Mar 2021
Abstract
We consider the problem of designing succinct encodings for some intersection graphs on a circle, which include graph classes such as circle graphs, k-polygon-circle graphs, circle-trapezoid graphs among others. More specifically, we first prove a general counting lower bound, which is of independent interest, for these intersection graph classes, and then present a uniform encoding approach that lets us obtain matching lower and upper bounds for their succinct representation.
Metrics
Details
- Title
- Succinct representations of Intersection Graphs on a Circle
- Creators
- Huseyin Acan - Drexel UniversitySankardeep Chakraborty - National Institute of InformaticsSeungbum Jo - Chungbuk National UniversityKei Nakashima - University of TokyoKunihiko Sadakane - University of TokyoSrinivasa Rao Satti - Norwegian University of Science and Technology
- Publication Details
- 2021 Data Compression Conference (DCC), v 2021-, pp 123-132
- Publisher
- IEEE
- Grant note
- NRF-2020R1 G1A1101477 / Korea government (MSIT) (10.13039/100000964) 18H05291 / JSPS KAKENHI (10.13039/100000964)
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000675592800013
- Scopus ID
- 2-s2.0-85106066471
- Other Identifier
- 991019168431104721
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
- Imaging Science & Photographic Technology