On Compact Encoding of Pagenumber $k$ Graphs
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 ed...
| Hoofdauteurs: | , |
|---|---|
| Formaat: | Artikel |
| Taal: | English |
| Gepubliceerd in: |
Discrete Mathematics & Theoretical Computer Science
2008-01-01
|
| Reeks: | Discrete Mathematics & Theoretical Computer Science |
| Onderwerpen: | |
| Online toegang: | https://dmtcs.episciences.org/436/pdf |