### A geometric-graphs offering

**Introduction**

*8-neighborhood (*or

*Moore) graph:*

*wrong*about it: it

*distorts distances*in the plane.

*embedding*of $G$ if $|| F(u) - F(v)||_2 \geq d_G(u, v)$ for all distinct vertices $u, v$. (This is just a normalization convention.) Define the

*distortion*of $F$ as the maximum (supremum) of

*approximation algorithms*for NP-hard problems

*.*My initial focus here will be on embeddings for

*periodic*and

*highly-symmetric*graphs like $G_{8N}$.

**Warm-up:**Show that $\sqrt{2}$ is the minimum distortion of

*any*embedding of the 8-neighborhood graph $G_{8N}$.

**Symmetries and Distortion**

*always*the case.

*automorphism*of $G$ is a bijective mapping $\phi$ from $V(G)$ to itself, such that $(u, v) \in E(G) \Leftrightarrow (\phi(u), \phi(v)) \in E(G)$.

*2D symmetry*if there's an embedding $F$ of $V(G)$ into the plane, and linearly independent vectors $\mathbf{p}, \mathbf{q} \in \mathbf{R}^2$, such that a translation of the plane by $\mathbf{p}$ or by $\mathbf{q}$ induces an automorphism of $G$ (in the obvious way). In this case we also say the embedding $F$ has 2D symmetry.

**Question 1:**Suppose $G$ has 2D symmetry. Does this imply that there is a distortion-minimizing embedding of $G$ with 2D symmetry?

*transitive*if "all points look the same:" there's an automorphism of $G$ mapping any vertex $u$ to any other desired vertex $v$. Similarly, say that an embedding $F$ of $G$ is transitive, if translating the plane by any vector of form $(F(u) - F(v))$ induces an automorphism of $G$. (The usual embedding of $G_{8N}$ is transitive.)

**Question 2:**Suppose $G$ has 2D symmetry and is transitive. Is there a distortion-minimizing, transitive embedding of $G$ with 2D symmetry?

**Question 3:**Suppose $G$ has 2D symmetry, and is presented to us (in the natural way, by a finite description of a repeating "cell"). What is the complexity of determining the minimum distortion of any embedding of $G$? What about the case where $G$ is also transitive?

**Graph Metrics and Movement**

*4-neighborhood*graph $G_{4N}$. It's not hard to see that the minimum-distortion embedding of $G_{4N}$

*also*has distortion $\sqrt{2}$. (You have to blow up the grid by a $\sqrt{2}$ factor to make the diagonals long enough.) Yet $G_{4N}$ seems considerably more

*natural*as a discrete representation of movement in the plane somehow. Why?

*do*correspond to distances in the graph $G_{8N}$! This is so,

*even if*we're allowed to switch paths at the crossover points.

*obstructed-plane graph,*if there is an embedding of $G$ into $\mathbf{R}^2$ along with a set of "obstructions" (just a point-set in $\mathbf{R}^2$), such that shortest paths in $G$ correspond to shortest obstruction-avoiding paths in $\mathbf{R}^2$.

**Question 4:**What is the complexity of deciding whether a given graph (finite, say) is an obstructed-plane graph?

*except*the intended shortest paths between all pairs of points. Using this observation, we can at least show that our problem is in NP. Is it NP-complete?

**Question 5:**Is the necessary condition above also sufficient?

*without*changing the topological structure of the drawing, in order to get the desired obstructed-plane realization.

Labels: complexity, geometry