Mike McGeachie (Macalester '99) and Joan Hutchinson (Macalester math dept.) suggested the following model for graph embedding:

A "polar visibility graph" is a network (graph) whose vertices are closed arcs of circles centered at the origin, with two arcs considered to be adjacent if they can see each other along a radial line, possibly passing through the origin. But this visibility must be at more than just a single point.

For example, let B, the basic graph for this problem, be as in the figure below.

1 /|\ / | \ 4 2 5 \ | / \|/ 3Then it is not hard to find a polar visibility representation of B. Just use the five arcs centered at the origin defined by the following radius, angle-interval pairs (in degrees):

(1, [0, 180]) (2, [0, 45]) (3, [0, 60]) (2.5, [45,70]) (4, [-60,30]).

Now take B and add vertices 6, 13, 12, 10, 8 that are adjacent to 1, 2, 3, 4, and 5, respectively. Then add vertex 7 adjacent to 6, 14 adjacent to 13, 11 adjacent to 10, and 9 adjacent to 8. In short, add an arm and a hand to vertices 1, 2, 4, and 5, and an arm only to vertex 3. This yields:

7 | | 6 | | 1 /|\ / | --------- / | \ 11 ---- 10 ---- 4 2---13---14 5 ---- 8 ---- 9 \ | / \ | --------/ \|/ 3 | | 12Is there a PVG representation of this 14-vertex graph?

The three bits of code at the end of this message generate three diagrams relevant to this problem:

1. The basic 5-vertex graph.

© Copyright 1999 Stan Wagon. Reproduced with permission.

2. The 14-vertex graph.

3. A PVG representation of the basic graph.

12 October 1999