We study two notions that refers to asymmetric graphs, which we view as graphs having a unique ordering that can be reconstructed by looking at an unlabeled version of the graph.
A local self-ordering procedure for a graph $G$ is given oracle access to an arbitrary isomorphic copy of $G$, denoted $G'$, and a vertex $v$ in $G'$, and is required to identify the name (or location) of $v$ in $G$, while making few (i.e., polylogarithmically many) queries to $G'$. A graph $G=(V,E)$ is robustly self-ordered if the size of the symmetric difference between $E$ and the edge-set of the graph obtained by permuting $V$ using any permutation $\pi:V\to V$ is proportional to the number of non-fixed-points of $\pi$ and to the maximal degree of $G$; that is, any permutation of the vertices that displaces $t$ vertices must ``displace'' $\Omega(t\cdot d)$ edges, where $d$ is the maximal degree of the graph.
We consider the relation between these two notions in two regimes: The bounded-degree graph regime, where oracle access to a graph means oracle access to its incidence function, and the dense graph regime, where oracle access to the graph means access to its adjacency predicate.
We show that, in the bounded-degree regime, robustly self-ordering and local self-ordering are almost orthogonal; that is, even extremely strong versions of one notion do not imply very weak versions of the other notion. Specifically, we present very efficient local self-ordering procedures for graphs that possess derangements that are almost automorphisms (i.e., a single incidence is violated). One the other hand, we show robustly self-ordered graphs having no local self-ordering procedures even when allowing a number of queries that is a square root of the graph's size.
In the dense graph regime, local self-ordering procedures are shown to yield a quantitatively weaker version of the robust self-ordering condition, in which the said proportion is off by a factor that is related to the query complexity of the local self-ordering procedure. Furthermore, we show that this quantitatively loss is inherent. On the other hand, we show how to transform any robustly self-ordered graph into one having a local self-ordering procedure, while preserving the robustness condition. Combined with prior work, this yields explicit constructions of graphs that are both robustly and locally self-ordered, and an application to property testing.