The Speeds of Families of Intersection Graphs

Overview

We consider a class of graphs called intersection graphs, which we can create from certain systems of geometric objects, such as line segments in a plane. Specifically, we are interested in one of the fundamental questions of graph theory: How many graphs with a certain property exist? Pach and Toth have previously proven the bounds on the number of intersection graphs of the more general curves in a plane. We investigate the more specific case of intersection graphs of systems of segments of parabolas, conic sections, polynomials, and rational functions. Pach and Solymosi obtained an upper bound on the number of intersection graphs of line segments, and Fox obtained essentially the same lower bound. We extend their techniques in combination with some new techniques to these various other systems. We obtain the bounds on the number of intersection graphs of these systems to be dependent on the degree of freedom, which colloquially is the number of variables needed to define each segment. The structure of these intersection graphs of planar curves is unknown, and Schaefer, Sedgwick, and Stefankovic have shown that recognizing such graphs is NP-complete. Intersection graphs have various applications in computer science and biology, through topics including sensor networks, physical mapping of DNA, and genome reconstruction. Intersection graphs as constructed from systems of geometric objects are particularly useful in describing other classes of graphs as well; for example, the recently proven Scheinerman’s conjecture states that all planar graphs are intersection graphs of line segments in the plane. As such, the number of intersection graphs of planar curves poses an interesting problem.

Competition history

• ISEF 2014 Robotics and Intelligent Machines · Entry MA023

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.