Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses

Details Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses

2001-02-07

arxiv.org/abs/cs/0102005v2

Computer Science

Data Structures and Algorithms

24 pages; 3 figures; a preliminary version appeared in the Proceedings of ICALP'98, LNCS 1443, pp. 118-129. (The 2nd version c

Scientific paper

Let G be a plane graph of n nodes, m edges, f faces, and no self-loop. G need not be connected or simple (i.e., free of multiple edges). We give three sets of coding schemes for G which all take O(m+n) time for encoding and decoding. Our schemes employ new properties of canonical orderings for planar graphs and new techniques of processing strings of multiple types of parentheses. For applications that need to determine in O(1) time the adjacency of two nodes and the degree of a node, we use 2m+(5+1/k)n + o(m+n) bits for any constant k > 0 while the best previous bound by Munro and Raman is 2m+8n + o(m+n). If G is triconnected or triangulated, our bit count decreases to 2m+3n + o(m+n) or 2m+2n + o(m+n), respectively. If G is simple, our bit count is (5/3)m+(5+1/k)n + o(n) for any constant k > 0. Thus, if a simple G is also triconnected or triangulated, then 2m+2n + o(n) or 2m+n + o(n) bits suffice, respectively. If only adjacency queries are supported, the bit counts for a general G and a simple G become 2m+(14/3)n + o(m+n) and (4/3)m+5n + o(n), respectively. If we only need to reconstruct G from its code, a simple and triconnected G uses roughly 2.38m + O(1) bits while the best previous bound by He, Kao, and Lu is 2.84m.

Affiliated with

Also associated with

No associations

Rating

Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-461528