Homework Set 2: Plane Graphs, Visibility, Euclidean and Taxicab Distance

Prepared by:

Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk

1. If G is a graph, a valence vector for G, (v1, v2, v3, v4, ... , vmax) is a non-negative integer vector where vi is the number of vertices of G with valence i. If G is a plane graph embedded in the plane, a face vector for G, (p3, p4, ... , pmax) is a non-negative integer vector where pi is the number of faces of G with i sides.

a. i. Draw (if possible) a plane graph with valence vector (4, 8, 6, 1)?

ii. What is the face vector of the graph you drew?

b. i. Draw (if possible) a graph with face vector (4, 8, 6, 1)?

ii. What is the valence vector of the graph you drew?

2. Given the simple polygon below:

a. Find the minimum number of vertex guards necessary to see all of this polygon.

b. Draw at least 4 inequivalent triangulations for this polygon and, using each of these triangulations, find the smallest number of vertex guards that a 3-coloring of the triangulation determines.

c. How many guards placed in the exterior of this polygon are necessary to guard the exterior of the polygon? .

3. Definition: A polygon is equilateral if all of its sides have the same length.

a. If possible draw a simple plane equilateral polygon with 6 sides which requires 2 guards.

b. If possible draw a simple plane equilateral polygon with 9 sides which requires 3 guards.

4. a. Sketch a diagram of the points whose Euclidean distance from (2, 2) and (6, 6) is the same.

b. Sketch a diagram of the points whose taxicab distance from (2, 2) and (6, 6) is the same.

c. Sketch a diagram of the points whose Euclidean distance from (0, 0) and (6, 8) is the same.

d. Sketch a diagram of the points whose taxicab distance from (0, 0) and (6, 8) is the same.

e. Sketch a diagram of the points whose Euclidean distance from (0, 0) and (2, 10) is the same.

f. Sketch a diagram of the points whose taxicab distance from (0, 0) and (2, 10) is the same.