In search for isotropic graphs: Straight lines and parallels

2010-11-22T10:48:18Z

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?

Answer by Joseph O'Rourke for In search for isotropic graphs: Straight lines and parallels

2010-11-22T13:09:07Z

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.

In search for isotropic graphs: Straight lines and parallels - MathOverflow

In search for isotropic graphs: Straight lines and parallels

Answer by Joseph O'Rourke for In search for isotropic graphs: Straight lines and parallels