Tata Institute of Fundamental Research
Hardness of Recognizing Geometric Intersection Graphs
STCS Student Seminar
Speaker:
Kshitij Gajjar (Technion - Israel Institute of Technology
Haifa, Israel.)
Organiser:
Prerona Chatterjee
Date:
Friday, 15 Jan 2021, 17:15 to 18:15
Venue:
(Scan to add to calendar)
Abstract:
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:
https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
| Speaker: | Kshitij Gajjar (Technion - Israel Institute of Technology Haifa, Israel.) |
| Organiser: | Prerona Chatterjee |
| Date: | Friday, 15 Jan 2021, 17:15 to 18:15 |
| Venue: |
(Scan to add to calendar)
Abstract:
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:
https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
No background other than high school geometry will be assumed for this talk.
This is joint work with Dibyayan Chakraborty.
Zoom link:
https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09