Orthogonal embeddings of graphs in Euclidean space

Wai Chee Shiu (Department of Mathematics, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong, P.R. China)
Richard M. Low (Department of Mathematics and Statistics, San Jose State University, San Jose, CA 95192, USA)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 7, No 2 (2019): Electronic Journal of Graph Theory and Applications

Let G = (V, E) be a simple connected graph. An injective function f : V → Rn is called an n-dimensional (or n-D) orthogonal labeling of G if uv, uw ∈ E implies that (f(v) − f(u)) ⋅ (f(w) − f(u)) = 0, where  ⋅  is the usual dot product in Euclidean space. If such an orthogonal labeling f of G exists, then G is said to be embedded in Rn orthogonally. Let the orthogonal rank or(G) of G be the minimum value of n, where G admits an n-D orthogonal labeling (otherwise, we define or(G) = ∞). In this paper, we establish some general results for orthogonal embeddings of graphs. We also determine the orthogonal ranks for cycles, complete bipartite graphs, one-point union of two graphs, Cartesian product of orthogonal graphs, bicyclic graphs without pendant, and tessellation graphs.