REU 2010 -- DIMACS Induced Planar Graphs |
---|

## Contact information

Timothy Hayes

Email: th1216@messiah.edu

## Project Description

Given an arrangment of lines in a two dimensional plane, within each region created by the lines a vertice is placed, and an edge
is placed among two vertices if the corresponding regions have a common boundary. The graph formed by this is called an induced
planar graph. The goal is to find which graphs are induced planar graphs.
Mentor: Gene Fiorini
Induced Planar Graph Introduction Presentation

Solution to Induced Planar Graph Problem, Final Presentation

## Progress Report

**Week 1 (June 1th - June 4th)**

- Arrived at Rutgers University. Introduced to multiple possible problems.

**Week 2 (June 7th - June 11th)**

- Created formulas that determined the number of edges, faces, and vertices given the number of lines, number
- of different angles of lines, number of intersection points, and other characteristiscs regarding these things
- Furthermore, I developed restrictions for the vertices and edges of these graphs but I don't like this very
- much because it only identifies graphs that don't work.

**Week 3 (June 14th - June 18th)**

- I developed a conjecture regarding how many times a line can cross and how this must match some characteristics of a graph.
- I also developed a computer program that calculates appropriate values regarding the conjecture. The only problem about the
- conjecture which establishes a relation between the arrangment of lines and a graph, is that one of the variables in the relation
- cannot (perhaps yet) be determined.

**Week 4 (June 21th - June 25th)**

- I wrote the paper on the conjecture and worked on a geometric problem that related close to it.

**Week 5 (June 28th - July 2nd)**

- Edited the paper and I am developing a more thorough symbolic approach to my solution. The geometric problem was settled and does
- not have very much impact because the conjecture itself changed.

**Week 6 (July 5th - July 9th)**

- The new paper was finished. Now I'm trying to develop a simplier approach to the problem.

**Week 7 (July 12th - July 16th)**

- Developed new approach using matrices. Finished final presentation.

**Week 8 (July 19th - July 23th)**

- Solution in matrice approach is near, may be able to come up with simple set of formulas.