In search for isotropic graphs: Straight lines and parallels - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T00:36:54Z http://mathoverflow.net/feeds/question/46930 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46930/in-search-for-isotropic-graphs-straight-lines-and-parallels In search for isotropic graphs: Straight lines and parallels Hans Stricker 2010-11-22T10:48:18Z 2010-11-22T14:23:16Z <p>I wonder why I can find only so little attempts of concisely defining "directions" and "isotropy" of graphs.</p> <p>In Euclidean spaces "directions" can be identified with equivalence classes of parallel straight lines. And on directions definitions of "isotropy" and "anisotropy" normally rely.</p> <p>I believe it's easy to define a "straight line" in a graph: </p> <p><strong>Definition 1:</strong> Let <em>$x$ be straightly connected to $y$</em> iff there is a unique (!) shortest path between vertices $x$ and $y$ of finite length. A <em>straight line</em> then is a maximal set of pairwise straightly connected vertices.</p> <p>Before I go to try to define parallelity I want to temporarily restrict the examination to infinite planar graphs whose faces tile the plane (<em>planar tiling graphs</em> for short) because these are the graphs I have in mind, finally. By doing so a straight line is additionally assumed to be infinite.</p> <p>Parallelity cannot be defined so unambiguously. Two definitions come to mind:</p> <p><strong>Definition 2.1:</strong> Let <em>two straight lines</em> $l_1$ <em>and</em> $l_2$ <em>be weakly parallel</em> iff they have no vertex in common. </p> <p>(This definition will definitely only make sense for planar graphs.)</p> <p><strong>Definition 2.2:</strong> Let <em>two straight lines</em> $l_1$ <em>and</em> $l_2$ <em>be strongly parallel</em> 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$.</p> <p>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.</p> <blockquote> <p><strong>Question 1:</strong> Can be seen at a glance whether the definitions above pass this litmus test?</p> <p><strong>Question 2:</strong> Are there known equivalent definitions (with different terminology only)?</p> <p><strong>Question 3:</strong> Are there known <em>other</em> definitions in the same spirit? </p> <p><strong>Question 4:</strong> Are there interesting results involving such definitions and maybe regularity and/or symmetry? </p> </blockquote> http://mathoverflow.net/questions/46930/in-search-for-isotropic-graphs-straight-lines-and-parallels/46946#46946 Answer by Joseph O'Rourke for In search for isotropic graphs: Straight lines and parallels Joseph O'Rourke 2010-11-22T13:09:07Z 2010-11-22T13:09:07Z <p>Perhaps it will help to explore the world of <em>pseudoline arrangements</em>. A <em>pseudoline</em> 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 <em>Levi Enlargement Lemma</em>: 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."</p> <p>Although pseudolines are mentioned in <a href="http://en.wikipedia.org/wiki/Arrangement_of_lines" rel="nofollow">this Wikipedia article</a>, a more definitive exposition can be found in the article by Jacob E. Goodman "Pseudoline arrangments," Chapter 5 in the <em><a href="http://cs.smith.edu/~orourke/books/discrete.html" rel="nofollow">Handbook of Discrete and Computational Geometry</a></em> (CRC, 2004). Another good source is the paper by Pankaj Agarwal and Micha Sharir, "<a href="http://portal.acm.org/citation.cfm?id=545381.545486" rel="nofollow">Pseudo-line arrangements: duality, algorithms, and applications</a>" <em>Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms</em>, 2002.</p>