Detecting a subdivision of a net
Presented by Mr. Nicolas TROTIGNON
Type: Oral presentation
Track: Algorithmic Graph Theory
The net is the graph made of a triangle with three non-incident pending edges. We give an O(n^17)-time algorithm that decides whether an input graph contains a subdivision of a net as an induced subgraph. Joint work with Maria Chudnovsky and Paul Seymour.