Involving \(d\)-convex simple and quasi-simple planar graphs in \(\mathbb R^3\) (Q812224)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Involving \(d\)-convex simple and quasi-simple planar graphs in \(\mathbb R^3\) |
scientific article |
Statements
Involving \(d\)-convex simple and quasi-simple planar graphs in \(\mathbb R^3\) (English)
0 references
16 February 2006
0 references
From the text: ``We will say that a graph \(G=(X,U)\) is involved in a metric space \(X'\), if there exists an application \(\varphi: X\to X'\), such that any two adjacent vertexes \(x, y\) in \(G\) have the images \(\varphi(x)\) and \(\varphi(y)\) in \(X'\), that are of distance equal to \(1\). In other words, adjacent vertexes of graph \(G\) are transformed into elements of distance \(1\) of space \(X'\). The minimal dimension of a Euclidean space, where a graph \(G\) can be involved is called the dimension of \(G\) and is denoted \(\dim G\).'' The purpose of the paper is to prove that planar graphs which have non-trivially many vertices and do not contain non-trivially large metrically convex subsets (except the whole graph) have dimension \(3\). As is clear from the paper, by ``application'' the authors mean an injective mapping. Hence the problem, considered in the paper is closely related to the Erdős problem on unit distances, unit distance graphs, and their generalizations [see Sections 5.1 and 5.2 in \textit{P. Brass, W. Moser} and \textit{J. Pach}, Research problems in discrete geometry (Springer, New York) (2005; Zbl 1086.52001)].
0 references
metric space
0 references
unit distance graph
0 references
metrically convex
0 references