Orthogonal embeddings of graphs in Euclidean space

Wai Chee Shiu, Richard M. Low


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.


orthogonal labeling, graph embedding, orthogonal drawing, Euclidean space

Full Text:


DOI: http://dx.doi.org/10.5614/ejgta.2019.7.2.13


J.A. Bondy and U.S.R. Murty. Graph Theory with Applications, MacMillan, New York, (1976).

J.A. Gallian. A dynamic survey of graph labeling, Electron. J. Combin. 20 (2017), #DS6. [3] B. Immanuel and K.A. Sugeng. Orthogonal labeling, Indonesian Journal of Combinatorics. 1 (2016), 1-8.

W.C. Shiu and P.C.B. Lam. The Wiener number of the hexagonal net, Discrete Appl. Math. 73 (1997), 101-111.

W.C. Shiu and P.C.B. Lam. Wiener numbers of pericondensed benzenoid molecule systems, Congr. Numer. 126 (1997), 113-124.

W.C. Shiu and R.M. Low. The integer-magic spectra of bicyclic graphs without pendant, Congr. Numer. 214 (2012), 65-73.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats