Packing Trees into Planar Graphs

García, A. and Hernando, C. and Hurtado, Ferran and Noy, M. and Tejel, J. (1998) Packing Trees into Planar Graphs. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 383-390 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_83).

Full text not available from this repository.

Abstract

The main problem considered in this paper is the following: given two trees both with n vertices, whether it is possible to draw them on the plane with the same set of vertices without crossings and duplicated edges. We formulate this problem in terms of packing graphs and give the solution in several situations. We also solve related problems on drawing trees and cycles.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_83
Classifications:M Methods > M.900 Tree
P Styles > P.540 Planar
ID Code:123

Repository Staff Only: item control page

References

B. Bollobás, Extremal Graph Theory, in Handbook of Combinatorics, vol. II. R.L. Graham, M. Grötschel and L. Lovász (eds.), pp. 1231-1292, North-Holland (1995).

S.M. Hedetniemi and P.J. Slater, A note on packing two trees into Kn, Ars Combinatoria 11 (1981), 149-153.

M. Maheo, J.F. Saclé y M. Wozniak, Edge-disjoint placement of the trees, European J. of Combinatorics 17 (1996), 543-563.