×

Embedding of trees in Euclidean spaces. (English) Zbl 0639.05017

It is proved that for any tree T the vertices of T can be placed on the surface of a sphere in \(R^ 3\) in such a way that adjacent vertices have distance 1 and nonadjacent vertices have distance less than 1. This improves an earlier result of the last three authors (to appear in Discrete and Computational Geometry).
Reviewer: J.Širáň

MSC:

05C05 Trees
05C10 Planar graphs; geometric and topological aspects of graph theory
51M05 Euclidean geometries (general) and generalizations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Frankl, P., Maehara, H.: Embedding then-cube in lower dimensions. Europ. J. Comb.7, 221–225 (1986) · Zbl 0627.05038
[2] Frankl, P., Maehara, H.: The Johnson-Lindenstrauss lemma and the sphericity of some graphs. J. Comb. Theory (B) (to appear) · Zbl 0675.05049
[3] Maehara, H.: Space graphs and sphericity. Discrete Appl. Math.49, 55–64 (1984) · Zbl 0527.05028 · doi:10.1016/0166-218X(84)90113-6
[4] Maehara, H.: On the sphericity for the join of many graphs. Discrete Math.7, 311–313 (1984) · Zbl 0544.05022 · doi:10.1016/0012-365X(84)90169-9
[5] Reiterman, J., Rödl, V., Šiňajová, E.: Geometrical embeddings of graphs. Discrete Math. (to appear) · Zbl 0684.05018
[6] Reiterman, J., Rödl, V., Šiňajová, E.: Embeddings of graphs in Euclidean spaces. Discrete & Computational Geometry (to appear) · Zbl 0762.05038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.