a) Find a formula for the number of edges in a triangulation of the plane, projective plane, torus, and Klein bottle.
b) Find a triangulation of the projective plane with 6 vertices.
Please ensure that your name and student number appear on the assignment, which must be submitted in a folder.
| 1. Determine what conditions apply to the number of vertices, edges and faces of a projective graph, a toroidal graph, and a Klein bottle graph in which every vertex has degree k. |
| 2. Determine what conditions apply to the number of vertices, edges and faces of a self-dual projective graph, a self-dual toroidal graph, and a self-dual Klein bottle graph. If every vertex has degree k, what values of k are allowed? |
| 3. Consider the three representations of the Klein bottle as a+b+a+b-, a+a+b+b+, or a+a+c+b+b+c-. The Klein bottle is cut along a non-contractible Jordan curve. Show that there are at least three possible results. What are they? |
| 4. Find all embeddings of K5 and K6 on the projective plane. Draw the dual graph of each embedding. Show your work. |
| 5. The Klein bottle can be represented as a+b+a+b-. Find a drawing of K6 on this representation of the Klein bottle. Show your work. |
| 6. Construct the complement of L(K5), the line graph of K5, and find a nice drawing of it. Show your work. Do you recognize this graph? |
|
7. A triangulation of a surface is a graph, all of whose facial cycles are triangles.
For example, K4 is a triangulation of the plane. a) Find a formula for the number of edges in a triangulation of the plane, projective plane, torus, and Klein bottle. b) Find a triangulation of the projective plane with 6 vertices. |
| 8. The Klein bottle can be represented as a+b+a+b- or a+a+b+b+. Find a drawing of K3,3 U K3,3 on both representations. |
| 9. Construct an embedding of the Petersen graph on the torus, and find its dual. |
|
10. The torus is cut along the Jordan curve abc shown in the diagram. What is the result ?
|
| 11. Find a toroidal embedding of K6 and K7. Show your work. |
| 12. Find a projective embedding of K3,4 and find its dual. What graph is it? |
| 13. Starting with the projective embeddings of K5 and K6 of question 4, find their double covers as planar drawings. |
Program the crossover algorithm to search for a long path in the graphs of Question 8,
and for those shown below,
and for those in the additional input files listed.
Pseudo-code for the crossover algorithm follows.
find a uv-path P where u and v are both blocked
(ie, the path cannot be extended further from u or v)
do {
for each w --> u do {
x = vertex previous to w
look for a vertex z --> x, where z is not on P
if found, extend P, then go to L1
}
for each w --> v do {
y = vertex following w
look for a vertex z --> y, where z is not on P
if found, extend P, then go to L1
}
look for a crossover of order 1
if found, extend P
L1:
} until no extension of P was found
Choose the starting vertex randomly, and find a long path. Run the code in a loop
10 times, and print out the longest path found. Text forms of these graphs are available
as graph 1 and graph 2.
Additional input files are graph 3 and graph 4.
.