Problem of the Week 895

Polar Visibility

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
 \ | /
  \|/
   3

Then 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
            |
            |
            12

Is 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.
2. The 14-vertex graph.
3. A PVG representation of the basic graph.

© Copyright 1999 Stan Wagon. Reproduced with permission.