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.