Orthogonal embeddings of graphs in Euclidean space

Wai Chee SHIU, Richard M. Low

Research output: Contribution to journalJournal articlepeer-review


Let G = (V,E) be a simple connected graph. An injective function f: V Rn is called an ndimensional (or n-D) orthogonal labeling of G if uv, uw n 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) = 8). 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.

Original languageEnglish
Pages (from-to)373-381
Number of pages9
JournalElectronic Journal of Graph Theory and Applications
Issue number2
Publication statusPublished - 15 Oct 2019

Scopus Subject Areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

User-Defined Keywords

  • Euclidean space 2010 Mathematics Subject Classification
  • Graph embedding
  • Orthogonal drawing
  • Orthogonal labeling


Dive into the research topics of 'Orthogonal embeddings of graphs in Euclidean space'. Together they form a unique fingerprint.

Cite this