Abstract
The dimension of a graphG=(V, E) is the minimum numberd such that there exists a representation\(x \to \bar x \in R^d (x \in V)\) and a thresholdt such thatxy εE iff\(\mathop x\limits^ - \mathop y\limits^ - \geqslant t\). We prove that d(G)≤n−x(G) and\(d(G) \leqslant n - \sqrt n \) wheren=|V| andx(G) is the chromatic number ofG; we present upper bounds for the dimension of graphs with a large girth and we show that the complement of a forest can be represented by unit vectors inR 6. We prove that d(G)≥1/15n for most graphs and that there are 3-regular graphs with d(G)≥c logn/log logn.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. Frankl, H. Maehara, On the contact dimension of graphs, to appear.
P. Frankl, H. Maehara, The Johnson-Lindenstrauss lemma and the sphericity of some graphs, to appear.
H. Maehara, On the sphericity for the join of many graphs,Discrete Math. 49 (1984), 311–313.
H. Maehara, Space graphs and sphericity,Discrete Appl. Math. 7 (1984), 55–64.
H. E. Warren, Lower bounds of approximation by nonlinear manifolds.
V. Chvátal, P. L. Hammer, Aggregation of inequalities in integer programming,Ann. Discrete Math. 1 (1977), 145–162.
J. Reiterman, V. Rödl, E. Šiňajová, Geometrical embeddings of graphs,Discrete Math., to appear.
G. P. Egoryčev,Solution of the van der Waerden Problem for Permanents, IFSO 13M, Akad. Nauk SSSR.
D. I. Falikman, A proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix,Mat. Zametki 29 (1981), 931–938.
J. A. Bondy, U. S. R. Murty,Graph Theory with Applications, Macmillan, 1978.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Reiterman, J., Rödl, V. & Šiňajová, E. Embeddings of graphs in euclidean spaces. Discrete Comput Geom 4, 349–364 (1989). https://doi.org/10.1007/BF02187736
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187736