I wonder why I can find only so little attempts of concisely defining "directions" and "isotropy" of graphs.

In Euclidean spaces "directions" can be identified with equivalence classes of parallel straight lines. And on directions definitions of "isotropy" and "anisotropy" normally rely.

I believe it's easy to define a "straight line" in a graph:

Definition 1: Let $x$ be straightly connected to $y$ iff there is a unique (!) shortest path between vertices $x$ and $y$ of finite length. A straight line then is a maximal set of pairwise straightly connected vertices.

Before I go to try to define parallelity I want to temporarily restrict the examination to infinite planar graphs whose faces tile the plane (planar tiling graphs for short) because these are the graphs I have in mind, finally. By doing so a straight line is additionally assumed to be infinite.

Parallelity cannot be defined so unambiguously. Two definitions come to mind:

Definition 2.1: Let two straight lines $l_1$ and $l_2$ be weakly parallel iff they have no vertex in common.

(This definition will definitely only make sense for planar graphs.)

Definition 2.2: Let two straight lines $l_1$ and $l_2$ be strongly parallel iff there is a bijection $\pi$ from $l_1$ to $l_2$, such that $x$ and $\pi(x)$ have equal distance for all $x \in l_1$.

A litmus test for a good definition of "straight lines" and "parallels" might be whether a planar (tiling) graph can always be drawn such that straight graph lines are mapped on straight geometric lines and parallel graph lines on parallel geometric lines.

Question 1: Can be seen at a glance whether the definitions above pass this litmus test?

Question 2: Are there known equivalent definitions (with different terminology only)?

Question 3: Are there known other definitions in the same spirit?

Question 4: Are there interesting results involving such definitions and maybe regularity and/or symmetry?


Perhaps it will help to explore the world of pseudoline arrangements. A pseudoline is a simple curve in the projective plane that is topologically a line. Each pair of pseudoines in an arrangment meet at most once. The analog of "every two points determine a line" is the the Levi Enlargement Lemma: For every two distinct points not on the same pseudoline in an arrangement, there is a pseudoline passing through those two points that enlarges the arrangement. The natural graphs associated with pseuodline arrangements have been studied. I believe they correspond to your "infinite planar graphs whose faces tile the plane."

Although pseudolines are mentioned in this Wikipedia article, a more definitive exposition can be found in the article by Jacob E. Goodman "Pseudoline arrangments," Chapter 5 in the Handbook of Discrete and Computational Geometry (CRC, 2004). Another good source is the paper by Pankaj Agarwal and Micha Sharir, "Pseudo-line arrangements: duality, algorithms, and applications" Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, 2002.

| cite | improve this answer | |
  • 1
    $\begingroup$ "That is topologically a line" is a bit too vague to be useful as a definition. There are competing alternatives, and the Euclidean case is different, but I think the right definition in the projective plane is that a pseudoline is a simple closed curve that does not separate the plane. $\endgroup$ – David Eppstein Nov 22 '10 at 18:54
  • $\begingroup$ @David: Thanks, you are definitely correct! $\endgroup$ – Joseph O'Rourke Nov 22 '10 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.