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={n1, n2, n3, ...np} and L is a subset of  L the set of all pairs of distinct elements of N. (That is, L = N x N - {(ni,ni)} . ) 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 ni and nj , we say the nodes are adjacent or connected and write ni—nj .

Two graphs are considered isomorphic if there is a labelling of the nodes which preserves adjacency.

(That is, if G1=<N1,L1> and G2=<N1,L2> implies L1=L2.)

1.2 If each pair of successive nodes, (ni, ni+1), in a sequence of  nodes (n1, n2, n3, ...nk) 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, (ni, ni+1), in a sequence of distinct nodes (n1, n2, n3, ...nk) 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 Kn (in which each pair of nodes is connected) dG(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 Kn, 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 dG(n2, n4) >1. Then D(G) imposes the following order on edges:

dG(n1,n2) = 1
dG(n3,n4) =1
dG(n1, n3) 1
dG(n1, n4) 1
dG(n2, n3) 1
dG(n2, n4) >1.
crossing.gif (2955 bytes) dM(n1,n2) = d
dM(n3,n4) =d
then either
dM(n1, n3) <d
or dM(n1, n4) <d
or dM(n2, n3) <d
or dM(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 Kn) 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=dG(2,5)>dG(5,6)=2, but dM(2,5)<dM(5,6). The second drawing while planar, has the property that 3=dG(1,6)>dG(5,6)=2, but dM(1,6)<dM(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

cubes.gif (13704 bytes)

The standard drawing of Q3 in E3 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|xi - yi| 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 En if and only if it is monotonically embeddable in Mrn for the n-dimensional space defined by the Minkowski metric: d(x,y)=(S|xi - yi|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(Qn) = n.

1.8 Conjecture: MMD(Kn - l )=n-3.

2.0 A flavoring, F(G), of a graph G=<N,L> is an assignment F(ni)=vi to each ni in N, a vector vi=(xi1, xi2, ..., xiq ) e Rq .

Such a flavoring is said to be q-dimensional. A graph is said to be uniquely flavored if " i,j e N, i notequal j F(i) notequal 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=(w1, w2, ... wm) for wi e N is flavor-guided by a flavoring F(G) if the walk progresses according to some function f(F(wi)) which takes the flavor of each node wi, in turn, and produces, as output, the next node in the walk:

f(F(wi))= wi+1

The function f(F(G)) is called the guidance function of 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 w1and wm e N

there is walk W=(w1, w2, ... wm) guided by a simple guidance function f(F(wi))= wi+1 for which d(wi+1, wm)leqd(wi,wm).

2.5 A flavoring F of a graph G is called strongly sensitive if for every pair of nodes w1and wm e N

the walk produced by a simple guidance function produces a path of length d(w1,wm) from w1 to wm.