View in EDS PDF Full Text

On Compact Encoding of Pagenumber k Graphs.

Saved in:
Bibliographic Details
Title: On Compact Encoding of Pagenumber k Graphs.
Authors: Gavoille, Cyril1 gavoille@labri.fr, Hanusse, Nicolas1 hanusse@labri.fr
Source: Discrete Mathematics & Theoretical Computer Science (DMTCS). Dec2008, Vol. 10 Issue 3, p23-34. 12p. 3 Diagrams.
Subjects: Encoding, Paging (Computer science), Graphic methods, Embeddings (Mathematics), Routing (Computer network management)
Abstract: In this paper we show an information-theoretic lower bound of kn-o(kn) on the minimum number of bits to represent an unlabeled simple connected n-node graph of pagenumber k. This has to be compared with the efficient encoding scheme of Munro and Raman of 2kn + 2m + o(kn + m) bits (m the number of edges), that is 4kn + 2n + o(kn) bits in the worst-case. For m-edge graphs of pagenumber k (with multi-edges and loops), we propose a 2m log2 k + O(m) bits encoding improving the best previous upper bound of Munro and Raman whenever m ≤ &frac;kn/log2 k. Actually our scheme applies to k-page embedding containing multi-edge and loops. Moreover, with an auxiliary table of o(mlog k) bits, our coding supports (1) the computation of the degree of a node in constant time, (2) adjacency queries with O(log k) queries of type rank; select and match, that is in O(log k ⋅ min {log k= log log m; log log k}) time and (3) the access to δ neighbors in O(δ) runs of select; rank or match. [ABSTRACT FROM AUTHOR]
Copyright of Discrete Mathematics & Theoretical Computer Science (DMTCS) is the property of Discrete Mathematics & Theoretical Computer Science DMTCS and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:In this paper we show an information-theoretic lower bound of kn-o(kn) on the minimum number of bits to represent an unlabeled simple connected n-node graph of pagenumber k. This has to be compared with the efficient encoding scheme of Munro and Raman of 2kn + 2m + o(kn + m) bits (m the number of edges), that is 4kn + 2n + o(kn) bits in the worst-case. For m-edge graphs of pagenumber k (with multi-edges and loops), we propose a 2m log2 k + O(m) bits encoding improving the best previous upper bound of Munro and Raman whenever m ≤ &frac;kn/log2 k. Actually our scheme applies to k-page embedding containing multi-edge and loops. Moreover, with an auxiliary table of o(mlog k) bits, our coding supports (1) the computation of the degree of a node in constant time, (2) adjacency queries with O(log k) queries of type rank; select and match, that is in O(log k ⋅ min {log k= log log m; log log k}) time and (3) the access to δ neighbors in O(δ) runs of select; rank or match. [ABSTRACT FROM AUTHOR]
ISSN:13658050