Abstract
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 language | English |
---|---|
Pages (from-to) | 373-381 |
Number of pages | 9 |
Journal | Electronic Journal of Graph Theory and Applications |
Volume | 7 |
Issue number | 2 |
DOIs | |
Publication status | Published - 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