# 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.