Many graph problems that are NP-hard for general graphs can be solved in polynomial time for planar graphs. We explore the domain of "almost" planar graphs. These are graphs that can be made planar by removing one or two vertices from them. We show that recognition of intersection graphs for several different types of geometric objects in the plane (e.g., line segments, elliptical disks, rectangles, simple curves, etc.) is NP-hard, even if the inputs are restricted to almost planar graphs.
No background other than high school geometry will be assumed for this talk.
This is joint work with Dibyayan Chakraborty.
