Hardness of Recognizing Geometric Intersection Graphs


Kshitij Gajjar


Technion - Israel Institute of Technology
Haifa, Israel.


Friday, 15 January 2021, 17:15 to 18:15


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.

Zoom link: