Geometrical embeddings of graphs

DOI10.1016/0012-365X(89)90142-8zbMath0684.05018OpenAlexW2019029270MaRDI QIDQ1825202

Jan Reiterman, Vojtěch Rödl, Edita Šiňajová

Publication date: 1989

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(89)90142-8

zbMATH Keywords

treesforbidden induced subgraphssphericitythreshold dimensionscalar product dimensioncomplements of cyclesdistance dimensiongeneralized threshold graphsspherical dimension

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75)

Related Items

The geometry of graphs and some of its algorithmic applications, Embedding of trees in Euclidean spaces, Note on induced subgraphs of the unit distance graph \(E^ n\), Sphere and dot product representations of graphs, A note on vector representation of graphs, A combinatorial approach to complexity, On embedding of graphs into Euclidean spaces of small dimension, Unnamed Item, Sphericity, cubicity, and edge clique covers of graphs, On the contact dimensions of graphs, Embeddings of graphs in Euclidean spaces, The Colin de Verdière number and sphere representations of a graph, Learning centrality by learning to route, Monotone maps, sphericity and bounded second eigenvalue, Dispersed points and geometric embedding of complete bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Embedding the n-cube in lower dimensions
• Space graphs and sphericity
• On combinatorial properties of spheres in euclidean spaces
• A triangle free graph which cannot be \(\sqrt3\) imbedded in any Euclidean unit sphere
• Triangle free graphs that are not \(\sqrt{3}\)-embeddable in \(S^ n\).
• On embedding triangle-free graphs in unit spheres
• The Complexity of the Partial Order Dimension Problem
• On the Shannon capacity of a graph
• On the dimension of a graph