An Application of Well-Orderly Trees in Graph Drawing

Zhang, Huaming and He, Xin (2006) An Application of Well-Orderly Trees in Graph Drawing. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 458-467 (Official URL: http://dx.doi.org/10.1007/11618058_41).

Full text not available from this repository.

Abstract

Well-orderly trees seems to have the potential of becoming a powerful technique capable of deriving new results in graph encoding, graph enumeration and graph generation [3, 4]. In this paper, we reduce the height of the visibility representation of plane graphs from 5n/6 to (4n-1)/5, by using well-orderly trees.

Item Type:Conference Paper
Additional Information:10.1007/11618058_41
Classifications:P Styles > P.900 Visibility
M Methods > M.999 Others
ID Code:710

Repository Staff Only: item control page

References

G. di Battista, P. Eades, R. Tammassia, and I. Tollis: Graph Drawing: Algorithms for the Visualization of Graphs, Princeton Hall, 1998

N. Bonichon, B. Le Saec and M. Mosbah: Wagner's theorem on realizers, Proc. ICALP'02, Lecture Notes in Computer Science, Vol. 2380, (Springer, Berlin, 2002) 1043-1053.

N. Bonichon, C. Gavoille, and N. Hanusse: An triangulation, Proc. STACS'03, pp 499-510, Lectures Notes in Computer Science, Vol. 2607, Springer-Verlag, 2003.

N. Bonichon, C. Gavoille, and N. Hanusse: Canonical decomposition of outerplanar maps and application to enumeration, coding and generation, Proc. WG'2003, pp. 81-92, Lecture Notes in Computer Science, Vol. 2880, Springer-Verlag, 2003

H.-L. Chen, C.-C. Liao, H.-I. Lu and H.-C. Yen: Some applications of orderly spanning trees in graph drawing, Proc. Graph Drawing'02, pp. 332-343, Lecture Notes in Computer Science, Vol. 2528, Springer-Verlag, Berlin, 2002.

Y.-T. Chiang, C.-C. Lin and H.-I. Lu: Orderly spanning trees with applications to graph encoding and graph drawing, Proc. of the 12th Annual ACM-SIAM SODA, pp. 506-515, ACM Press, New York, 2001.

M. Chrobak and G. Kant: Convex grid drawings of 3-connected planar graphs, Technical Report RUU-CS-93-45, Department of Computer Science, Utrecht University, Holland, 1993.

U. Fößmeier, G. Kant and M. Kaufmann: 2-Visibility drawings of planar graphs, Proc. 4th International Symposium on Graph Drawing, pp. 155-168, Lecture Notes in Computer Science, Vol. 1190, Springer-Verlag, Berlin, 1996.

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

G. Kant: Drawing planar graphs using the lmc-ordering, Proc. 33rd Symposium on Foundations of Computer Science, pp.101-110, IEEE, Pittsburgh, 1992.

G. Kant: Algorithms for drawing planar graphs, Ph.D. Dissertation, Department of Computer Science, University of Utrecht, Holland, 1993.

G. Kant: Drawing planar graphs using the canonical ordering, Algorithmica 16 (1996), 4-32.

G. Kant: A more compact visibility representation. International Journal of Computational Geometry and Applications 7 (1997), 197-210.

G. Kant and X. He: Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoretical Computer Science 172 (1997), 175-193.

A. Lempel, S. Even and I. Cederbaum: An algorithm for planarity testing of graphs, Theory of Graphs (Proc. of an International Symposium, Rome, July 1966), pp. 215-232, Rome, 1967.

C.-C. Liao, H.-I. Lu and H.-C. Yen: Floor-planning via orderly spanning trees, Proc. 9th International Symposium on Graph Drawing, pp. 367-377, Lecture Notes in Computer Science, Vol. 2265, Springer-Verlag, Berlin, 2002.

C.-C. Lin, H.-I. Lu and I-F. Sun: Improved compact visibility representation of planar graph via Schnyder's realizer, SIAM Journal on Discrete Mathematics, 18 (2004), 19-29.

P. Ossona de Mendez: Orientations bipolaires. PhD thesis, Ecole des Hautes Etudes en Sciences Sociales, Paris, 1994.

P. Rosenstiehl and R. E. Tarjan: Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom. 1 (1986), 343-353.

W. Schnyder: Planar graphs and poset dimension. Order 5 (1989), 323-343.

W. Schnyder: Embedding planar graphs on the grid, Proc. of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 138-148, SIAM, Philadelphia, 1990.

R. Tamassia and I.G.Tollis: An unified approach to visibility representations of planar graphs. Discrete Comput. Geom. 1 (1986), 321-341.

H. Zhang and X. He: Compact Visibility Representation and Straight-Line Grid Embedding of Plane Graphs, Proc. WADS'03, Lecture Notes in Computer Science, Vol. 2748, (Springer-Verlag Heidelberg, 2003) 493-504.

H. Zhang and X. He: On Visibility Representation of Plane Graphs, Proc. STACS'04, Lecture Notes in Computer Science, Vol. 2996, (Springer-Verlag Heidelberg, 2004) 477-488.

H. Zhang and X. He: New Theoretical Bounds of Visibility Representation of Plane Graphs, Proc. GD'2004, Lecture Notes in Computer Science, Vol. 3383, (Springer-Verlag, 2005) pp. 425-430.

H. Zhang and X. He: Improved Visibility Representation of Plane Graphs, Discrete Comput. Geom. 30 (2005), 29-29.