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


  • 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