|REU 2010 -- DIMACS Induced Planar Graphs
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
- 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.