Compact Encodings of Planar Orthogonal Drawings

Chanda, Amrita and Garg, Ashim (2002) Compact Encodings of Planar Orthogonal Drawings. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 174-185 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_17).

Full text not available from this repository.

Abstract

We present time-efficient algorithms for encoding (and decoding) planar orthogonal drawings of degree-4 and degree-3 biconnected and triconnected planar graphs using small number of bits. We also present time-efficient algorithms for encoding (and decoding) turn-monotone planar orthogonal drawings.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_17
Classifications:G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.540 Planar
ID Code:229

Repository Staff Only: item control page

References

R.C. Chuang, A. Garg, X. He, M.Y. Kao, and H. Lu. Compact encoding of planar graphs via canonical ordering and multiple parenthesis. In Proc. International Colloqium on Automata, Languages and Programming (ICALP), pp. 118-129, 1998.

H. de Fraysseix. J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41-51, 1990.

G. Di Battista, G. Liotta, and F. Vargiu. Diagram Server. J. Visual Lang. Comput., 6(3):275-298, 1995.

G. Di Battista, G. Liotta, and F. Vargiu. Spirality and optimal orthogonal drawings. SIAM J. Comput., 27(6):1764-1811, 1998.

Xin He, M.-Y. Kao, and H. Lu. A fast general methodology for information-theoretically optimal encodings of graphs. SIAM J. Comput., 30(3):838-846, 2000.

G. Kant. Drawing planar graphs using lmc-ordering. In Proc. 33th Annu. IEEE Sympos. Found. Comput. Sci., pages 101-110, 1992.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput., 16(3):421-444, 1987.

R. Tamassia and I.G. Tollis. Planar grid embedding in linear time. IEEE Trans. Circuits Syst., CAS-36(9):1230-1234, 1989.

W.T. Tutte. A census of planar triangulation. Canad. J. Math., 14:21-38, 1962.