We develop a methodology for absolute encoding of spherical motion. This is accomplished by painting the surface of a moving sphere in two colors and sensing the color at a finite set of points. We show how point measurements on the sphere can resolve an arbitrary rotation to within a range depending on the number of sensors and the painting of the sphere. These techniques are applied to a prototype. The implementation of this prototype is discussed.

We present a technique for determining the absolute x, y-location of a robot in a workspace. The floor of the workspace is tiled with black and white squares in a pattern based on a variant of a de Bruijn sequence. The black/white pattern on the floor is read by a modest number of inexpensive, discrete optical sensors, and a simple algorithm determines the position of the robot.

This paper shows that every 3-connected planar graph G can be represented as a collection of circles, one circle representing each vertex and each face, so that, for each edge of G, the four circles representing the two endpoints and the two neighboring faces meet at a point, and furthermore the vertex-circles cross the face-circles at right angles. This extends a result of W. Thurston [The Geometry and Topology of Three Manifolds, unpublished] and, independently, Andreev. From this we deduce two corollaries: (1) The partial order formed by taking the vertices, edges, and bounded faces of G, ordered by inclusion, is a circle order; (2) One can represent G and its dual simultaneously in the plane with straight-line edges so that the edges of G cross the dual edges at right angles. This answers a question first asked by W. Tutte [Proc. LMS, 13 (3) (1963), pp. 743–768].

Given a hereditary (closed under taking induced subgraphs) class of graphs $\mathcal{P}$, the $\mathcal{P}$-chromatic number of a graph G, denoted $\chi _\mathcal{P} ( G )$, is defined to be the least integer k such that $V( G )$ admits a partition into k subsets each of which induce a member of $\mathcal{P}$. The $\mathcal{P}$-chromatic number of random graphs G on n vertices with fixed edge probability $0 < p < 1$ is studied and it is shown that $\chi _\mathcal{P} ( G ) \sim cn$ in case $\mathcal{P} < \infty $ and $\chi _\mathcal{P} ( G ) = \Theta ( n/\log n )$ in case $| \mathcal{P} | = \infty $. Also considered are generalized edge chromatic numbers.

A partially ordered set P is called a circle order if one can assign to each element $a \in P$ a circular disk in the plane $C_a $ so that $a < b$ and only if $C_a \subset C_b $. To a graph $G = ( V,E )$ associate a poset $P( G )$ whose elements are the vertices and edges of G. $v < e$ in $P( G )$ exactly when $v \in V, e \in E$, and v is an endpoint of e. It is shown that G is planar if and only if $P( G )$ is a circle order.

Masson and Morris [G.M. Masson and S.B. Morris IEEE Trans. Comput. C-32 (1983), pp. 649–657] introduced the notion of expected capacity of a concentrator and explicitly computed the expected capacity of $\left( {\begin{array}{*{20}c} n \\ 2 \\ \end{array} } \right)$-concentrators for values of n up to 15. In this article, tools from random graph theory are employed to find asymptotic expressions for the expected capacity for this class of concentrators. It is shown that the same results can be obtained by concentrators that are constructed at random. It also is shown that the expected capacity of random concentrators is slightly inferior to the expected capacity of Pippenger’s modular concentrators [N. Pippenger, Expected capacity of modular concentrators, preprint], and that random concentrators have certain advantages over deterministic designs. Finally, it is shown that expected capacity of a concentrator is actually a useful performance measure because the capacity of almost all input sets is very near the expected capacity.

One vertex of a graph has a message which it wishes to disseminate to all the other vertices in a graph. At each discrete time unit, a vertex can transmit a message to one of its neighbors. How long does it take for the message to be broadcast to all other vertices? We show that for sparse random graphs, near-optimal broadcast can be expected and for slightly denser graphs, true optimal broadcast occurs.

We analyze the PMC [10] model for fault tolerant systems by means of random directed graphs. Previous work has shown that the minimum in-degree of the testing digraph had to exceed the expected number of faulty units (vertices). We show, for much sparser digraphs than those described above, that the asymptotic probability of correct diagnosis of a faulty system tends to 1. Specifically we show that if our directed graph has n vertices, arc probability $p = {{(c\log n)} / n}$ and vertex failure probability $q < \frac{1}{2}$ then a simple algorithm will correctly diagnose the system “almost always” when ${{c > 1} / {(1 - q)}}$. However, when ${{c < 1} / {(1 - q)}}$ no algorithm can correctly diagnose the system. We present a similar analysis for a family of directed graphs which are not random. We conclude with analogous results for undirected graphs.