Some Applications of Orderly Spanning Trees in Graph Drawing

Chen, Ho-Lin and Liao, Chien-Chih and Lu, Hsueh-I. and Yen, Hsu-Chun (2002) Some Applications of Orderly Spanning Trees in Graph Drawing. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 332-343 (Official URL:

Full text not available from this repository.


Orderly spanning trees seem to have the potential of becoming a new and promising technique capable of unifying known results as well as deriving new results in graph drawing. Our exploration in this paper provides new evidence to demonstrate such a potential. Two applications of the orderly spanning trees of plane graphs are investigated. Our first application deals with Podevs drawing, i.e., planar orthogonal drawing with equal vertex size, introduced by Fößmeier and Kaufmann. Based upon orderly spanning trees, we give an algorithm that produces a Podevs drawing with half-perimeter no more than {\left\lceil{\frac{3n}{2}}\right\rceil}+ 1 and at most one bend per edge for any n-node plane graph with maximal degree \Delta, a notable improvement over the existing results in the literature in terms of the size of the drawing area. The second application is an alternative proof for the sufficient and necessary condition for a graph to admit a rectangular dual, i.e., a floor-plan using only rectangles.

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

Repository Staff Only: item control page


P. Bertolazzi, G. Di Battista, and W. Didimo. Computing orthogonal drawings with the minimum number of bends. IEEE Transactions on Computers, 49(8):826-840, 2000.

T. Biedl and M. Kaufmann. Area-efficient static and incremental graph drawings. In Proceedings of the 5th European Symposium on Algorithms, Lecture Notes in Computer Science 1284, pages 37-52. Springer-Verlag, 1997.

T. Biedl, B. Madden, and I. Tollis. The three-phase method: A unified approach to orthogonal graph drawing. International Journal of Computational Geometry and Applications, 10(6):553-580, 2000.

N. Bonichon, B. Le Saëc, and M. Mosbah. Orthogonal drawings based on the stratification of planar graphs. In Proceedings of the 6th International Conference on Graph Theory, Electronic Notes in Discrete Math 5, Marseille, France, 2000. Elsevier. A full version can be found at

Y.-T. Chiang, C.-C. Lin, and H.-I. Lu. Orderly spanning trees with applications to graph encoding and graph drawing. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 506-515, Washington, D.C., USA, 7-9 Jan. 2001. A revised and extended version can be found at

M. Chrobak and G. Kant. Convex grid drawings of 3-connected planar graphs. International Journal of Computational Geometry & Applications, 7(3):211-223, 1997.

M. Chrobak and T.H. Payne. A linear-time algorithm for drawing a planar graph on a grid. Information Processing Letters, 54(4):241-246, May 1995.

H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. On triangle contact graphs. Combinatorics, Probability and Computing, 3:233-246, 1994.

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

G. Di Battista, P. Eades, R. Tamassia, and I. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1998.

M. Eiglsperger and M. Kaufmann. Fast compaction for orthogonal drawings with vertices of prescribed size. In Mutzel et al. [27], pages 124-138.

U. Fößmeier, G. Kant, and M. Kaufmann. 2-visibility drawings of planar graphs. In S. North, editor, Proceedings of the 4th International Symposium on Graph Drawing, Lecture Notes in Computer Science 1190, pages 155-168, California, USA, 1996. Springer-Verlag.

U. Fößmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In S. Whitesides, editor, Proceedings of the 3th International Symposium on Graph Drawing, Lecture Notes in Computer Science 1027, pages 254-266, Passau, Germany, 1995. Springer-Verlag. A full version: Technical Report WSI-95-21, Wilhelm-Schickard-Institut, Universität Tübingen, 1995.

R.L. Francis and J.A. White. Facility layout and location. Prentice-Hall, New Jersey, 1974.

X. He. On floor-plan of plane graphs. SIAM Journal on Computing, 28(6):2150-2167, 1999.

X. He. A simple linear time algorithm for proper box rectangular drawings of plane graphs. Journal of Algorithms, 40(1):82-101, 2001.

O.H. Ibarra and L. Zhang, editors. Proceedings of the 8th International Conference on Computing and Combinatorics, Lecture Notes in Computer Science 2387, Singapore, August 15-17 2002. Springer.

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

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

K. Kozminski and E. Kinnen. Rectangular duals of planar graphs. Networks, 15(2):145-157, 1985.

K.A. Kozminski and E. Kinnen. Rectangular dualization and rectangular dissections. IEEE Transactions on Circuits and Systems, 35(11):1401-1416, 1988.

Y.T. Lai and S.M. Leinwand. A theory of rectangular dual graphs. Algorithmica, 5(4):467-483, 1990.

C.-C. Liao, H.-I. Lu, and H.-C. Yen. Floor-planning via orderly spanning trees. In Mutzel et al. [27], pages 367-377.

H.-I. Lu. Improved compact routing tables for planar networks via orderly spanning trees. In Ibarra and Zhang [17], pages 57-66.

K. Mailing, S.H. Mueller, and W.R. Heller. On finding most optimal rectangular package plans. In Proceedings of the 19th Annual IEEE Design Automation Conference, pages 263-270, 1982.

N. Mosbah, N. Bonichon, and B. Le Saëc. Wagner's theorem on realizers. In M. Hennesy and P. Widmayer, editors, Proceedings of the 29th International Colloqium on Automata, Languages, and Programming, Lecture Notes in Computer Science 1443, pages 1043-1063, Málaga, Spain, 2002. Springer-Verlag.

P. Mutzel, M. Jünger, and S. Leipert, editors. Proceedings of the 9th International Symposium on Graph Drawing, Lecture Notes in Computer Science 2265, Vienna, Austria, Springer.

P. Mutzel and R. Weiskircher. Bend minimization in orthogonal drawings using integer programming. In Ibarra and Zhang [17] , pages 484-493.

R. Otten. Efficient floorplan optimization. In Proceedings of International Conference on Computer Design, pages 499-503, Port Chester, New York, 1983.

A. Papakostas and I.G. Tollis. Effcient orthogonal drawings of high degree graphs. Algorithmica, 26(1):100-125, 2000.

M.S. Rahman, S. Nakano, and T. Nishizeki, Box-rectangular drawings of plane graph. In Proceedings of the 21st Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 1272, pages 250-261. Springer-Verlag, 1999.

W. Schnyder. Embedding planar graphs on the grid. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 138-148, 1990.

N. Sherwani. Algorithms for VLSI physical design automation. Kluwer Academic Publishers, 1995.

L. Stockmeyer. Optimal orientation of cells in slicing floorplan designs. Information and Control, 57(2):91-101, 1983.

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

S. Tsukiyama, K. Koike, and I. Shirakawa. An algorithm to eliminate all complex triangles in a maximal planar graph for use in VLSI floorplan. In Proceedings of the IEEE International Symposium on Circuits and Systems, pages 321-324, 1986.

K.-H. Yeap and M. Sarrafzadeh. Floor-planning by graph dualization: 2-concave rectlinear modules. SIAM Journal on Computing, 22(3):500-526, 1993.