**Introduction:**

Much current work in the human-computer interface considers the difficulty of navigating in either Euclidean space (e.g., CAD worlds), or non-Euclidean space (e.g., hypertexts).

As humans navigate through familiar Euclidean space, we rely upon directional cues such as gravity (e.g., to determine up from down). Many species seem to possess tropic and/or perceptual mechanisms that are gravitationally sensitive (reference). Others may possess magnetic sensitivity, though whether this is tropistic or teratogenic may be a subject of some debate. (reference) Certainly humans' invention of the compass has served to augment navigation by giving enhanced perceptual access to directional cues on the surface of the earth. Though this invention has improved our perception of direction, humans have, since earlier times, relied on landmarks such as astronomical objects to infer points of the compass as is evidenced by the fact that most cultures developed terminology for "north", "east", "south" and "west" long before the development of the compass.

Many studies have looked at the nature of human's "mental maps," or the internal representations we use to guide navigation (reference to review article). Differing methodologies have focused on the acquisition of new spatial information as well as on the nature of enduring spatial information such as driving in one's home town.

In a Euclidean or even a generalized Minkowski space (defn.) it stands to reason that a portion of humans' navigation could be supported by the intrinsically axial (or dimensional) quality of the space. That is, in a space that has axes, direction is an easily defined construct. Oftentimes graphs are studied and categorized according to how they can be embedded in axial spaces (see Harary distance in graphs). Hence we study the planarity, the genus, the folding number, the page number, or the dimensioanlity of graphs. Alternatively, Dailey (1994) also investigated graphs as containers of discrete metric spaces. Given that the distances in any finite metric space may be modeled by constructing a graph in which the set of points of the metric space is a subset of the nodes of a graph and in which the graphical distance preserves the distances in the metric space, graphs may be seen as a general model for all finite metric spaces.

Much of the work in visualization of graphs (review article) has to do with defining the goodness of their embedding in simple topological manifolds. But what of more abstract metric spaces or graphs that are not easily visualized through embeddings in more traditional spaces? May such spaces nevertheless contain (or allow the induction of) field effects such as gravity and magnetism? A generalization of the concepts of direction and landmarks to arbitrary metric spaces (non-dimensional spaces) is considered.

A study by Dailey (1984), showed that three-connected planar four-regular graphs have an invariant feature known as the tangle-number. The tangle number is determined by walking forward through the graph, orienting the four lines clockwise starting with the direction the current node has been entered and always choosing the line opposite the line of entry. Accordingly, planar embeddings of graphs may be seen to possess a semblance of "directionality" that is relatively independent of the coordinates of the embedding. The discussion of generalizing the concept of direction to graphs is thus motivated.

**1.0** A **graph** G=<N,L> is a symmetric,
antireflexive binary relation on a set of nodes N. That is, N is a set, N={n_{1},
n_{2}, n_{3}, ...n_{p}} and L is a subset of L the set of all pairs of distinct elements of N.
(That is, L = N x N - {(n_{i},n_{i})}
. ) Elements of N are called **nodes**; elements of L are called **lines**.
The number of nodes as defined above is often denoted by the letter **p**,
sometimes called the **size of the graph**.

**1.1** If there is a line between two nodes n_{i} and n_{j}
, we say the nodes are **adjacent** or **connected** and write n_{i}—n_{j}
.

Two graphs are considered

isomorphicif there is a labelling of the nodes which preserves adjacency.(That is, if G

_{1}=<N_{1},L_{1}> and G_{2}=<N_{1},L_{2}> implies L_{1}=L_{2}.)

**1.2** If each pair of *successive* nodes, (n_{i}, n_{i+1}),
in a sequence of nodes (n_{1}, n_{2}, n_{3}, ...n_{k})
is connected, then the sequence is called a **walk**. The number of lines in
a path is called the **length** of the walk. Note that a walk may contain a
given node more than once.

**1.3 **If each pair of *successive* nodes, (n_{i}, n_{i+1}),
in a sequence of *distinct* nodes (n_{1}, n_{2}, n_{3},
...n_{k}) is connected, then the sequence is called a **path**.
The number of lines in a path is called the **length** of the path. The
length of the shortest path between two nodes is called the **distance**
between the nodes.

**1.4 **A graph is called planar if it can be drawn in the plane without
crossing lines.

While deciding if a given graph is planar or not can be computed in time linearly related to the number of nodes (Tarjan & Hopcroft, 1974), the issue of minimizing the number of crossing lines for a given non-planar graph is NP-complete (reference), implying that finding "good" drawings of graphs in the plane is non-trivial. If a three-dimensional embedding of a graph were to contain two lines which coincide at a point, we may easily nudge any of the four affected nodes along the axis perpendicular to the plane in which the lines were drawn, preserving adjacency but removing the crossing. Hence, in a sense, all graphs may be embedded in 3-space withough crossing lines. Hence investigations of higher dimensional embeddings have generally been confined to the drawing of graphs in n-dimensional space under certain constraints on the lengths of lines.

We consider a generalization of "good" embeddings of graphs in higher dimensional space.

**1.5 **Consider all pairs of nodes in a connected graph and construct two
distances for each pair: the graphical distance D(G) (e.g. the minimum pathwise distance
between the nodes) and the embedding distance D(M) (e.g. the distance in the metric space
M in which the graph is drawn, we may then put those pairs in nondecreasing order on the
variable D(G). If the resulting vector for D(M) is monotonic nondecreasing as well, then
we will say the embedding is **monotonically consistent**. Since the complete
graph K_{n} (in which each pair of nodes is connected) d_{G}(ni, nj)=1 is
monotonically consistent for any embedding in a metric space, we will restrict the
discussion to graphs which are proper subgraphs of K_{n}, unless otherwise
specified.

Example: No embedding of K4 - l in E1 is monotonically consistent.

Example: suppose in Euclidean 2-space, we have two crossing lines: the line (n1,n2)
crosses the line (n3,n4) and that we have at least two non-adjacent nodes d_{G}(n2,
n4) >1. Then D(G) imposes the following order on edges:

d _{G}(n1,n2) = 1

d_{G}(n3,n4) =1

d_{G}(n1, n3) ³1

d_{G}(n1, n4) ³1

d_{G}(n2, n3) ³1

d_{G}(n2, n4) >1.d _{M}(n1,n2) = d

d_{M}(n3,n4) =d

then either

d_{M}(n1, n3) <d

or d_{M}(n1, n4) <d

or d_{M}(n2, n3) <d

or d_{M}(n2, n4) <d

However, since the lines cross, there is no way to position the four nodes such that D(M)
preserves the above ordering, hence the embedding is non-monotonic. This establishes the
following theorem:

**1.6** Theorem. Any embedding of a nonplanar graph (other than K_{n})
in the plane is non-monotonic. This follows trivially from the existence of two crossing
lines in any nonplanar graph and the above observations.

While nonplanarity is sufficient for non-monotonicity of embedding in Euclidean 2-space, the converse is not the case.

Example: The cube Q3 is planar but non-monotonic in 2-space. In the figure below, we
see two drawings of Q3 in the plane. The first drawing has the property that 3=d_{G}(2,5)>d_{G}(5,6)=2,
but d_{M}(2,5)<d_{M}(5,6). The second drawing while planar, has the
property that 3=d_{G}(1,6)>d_{G}(5,6)=2, but d_{M}(1,6)<d_{M}(5,6).
It is not difficult to see that any drawing of Q3 in the plane will possess such
monotonicities, since all four opposing pairs of vertices ((1,6), (3,8), (7,4) and (5,2))
of the cube must be maximally distant from one another

The standard drawing of Q3 in E_{3} is obviously monotonic. We may note that
none of the examples relies strictly on Euclidean distance, and generalizes easily to
"city block" distance as defined by d(x,y)=S|x_{i} - y_{i}| for example. I suspect,
likewise that any three-dimensional embedding of the standard hypercube Q4 is
non-monotonic.

Conjecture: a graph is monotonically embeddable in E_{n} if and only if it is monotonically embeddable in M^{r}_{n} for the n-dimensional space defined by the Minkowski metric: d(x,y)=(S|x_{i} - y_{i}|^{r})^{1/r}.

The above conjecture gives rise to the following definition:

**1.7** The** metric-monotonic dimension** MMD(G) of a graph
G is the minimum dimension of the Minkowski space in which the graph may be monotonically
embedded.

Conjecture: MMD(Q_{n}) = n.

1.8 Conjecture: MMD(K_{n} - l )=n-3.

**2.0** A** flavoring**, F(G), of a graph G=<N,L> is an
assignment F(n_{i})=v_{i} to each n_{i} in N, a vector v_{i}=(x_{i1},
x_{i2}, ..., x_{iq} ) e R^{q}
.

Such a flavoring is said to be

q-dimensional. A graph is said to beuniquely flavoredif " i,j e N, i j F(i) F(j).

**2.1** A one-dimensional flavoring of a graph is called **gravitational**
if " i,j e N such that d(i,j)=2
and F(i)<F(j)

$ k e N such that i—k and k—j and F(i)<F(k)<F(j).

**2.2** A walk W=(w_{1}, w_{2}, ... w_{m}) for w_{i}
e N is **flavor-guided** by a flavoring F(G) if
the walk progresses according to some function f(F(w_{i})) which takes the flavor
of each node w_{i}, in turn, and produces, as output, the next node in the walk:

f(F(w

_{i}))= w_{i+1}

The function f(F(G)) is called the

guidance functionof the flavor-guided walk..

**2.3** If the guidance function of a flavor-guided walk is monotonic on
F(G) then the function is called **simple**.

**2.4** A flavoring F of a graph G is called **sensitive** if
for every pair of nodes w_{1}and w_{m} e N

there is walk W=(w

_{1}, w_{2}, ... w_{m}) guided by a simple guidance function f(F(w_{i}))= w_{i+1}for which d(w_{i+1}, w_{m})d(w_{i},w_{m}).

**2.5** A flavoring F of a graph G is called **strongly sensitive**
if for every pair of nodes w_{1}and w_{m} e N

the walk produced by a simple guidance function produces a path of length d(w

_{1},w_{m}) from w_{1}to w_{m}.