Linear-time succinct encodings of planar graphs via canonical orderings

Authors
Citation
X. He et al., Linear-time succinct encodings of planar graphs via canonical orderings, SIAM J DISC, 12(3), 1999, pp. 317-325
Citations number
23
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Engineering Mathematics
Journal title
SIAM JOURNAL ON DISCRETE MATHEMATICS
ISSN journal
0895-4801 → ACNP
Volume
12
Issue
3
Year of publication
1999
Pages
317 - 325
Database
ISI
SICI code
0895-4801(1999)12:3<317:LSEOPG>2.0.ZU;2-H
Abstract
Let G be an embedded planar undirected graph that has n vertices, m edges, and f faces but has no self-loop or multiple edge. If G is triangulated, we can encode it using 4/3 m 1 bits, improving on the best previous bound of about 1.53m bits. In case exponential time is acceptable, roughly 1.08m bit s have been known to suffice. If G is triconnected, we use at most (2.5 + 2 log 3) min {n,f} 7 bits, which is at most 2.835m bits and smaller than the best previous bound of 3m bits. Both of our schemes take O(n) time for enc oding and decoding.