BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Irene Parada (TU Eindhoven) DTSTART:20210311T150000Z DTEND:20210311T170000Z DTSTAMP:20260422T065500Z UID:CJCS/7 DESCRIPTION:Title: Ins erting edges into simple drawings\nby Irene Parada (TU Eindhoven) as p art of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\nSimple dr awings of graphs are those in which each pair of edges share at most one p oint\, either a common endpoint or a proper crossing. Given a simple drawi ng D of a graph G\, in this talk we consider the problem of inserting a gi ven set of missing edges (edges of the complement of G) into D such that t he result is again a simple drawing. We show that it is NP-complete to dec ide whether one edge can be inserted into a simple drawing. On the positiv e side\, we present a Fixed-Parameter Tractable (FPT) algorithm for this p roblem parameterized by the number of crossings that the edge to be insert ed can have. This algorithm is tight under the Exponential Time Hypothesis . We also obtain an FPT algorithm for inserting a bounded number of edges with a bounded number of crossings. In these FPT algorithms\, after workin g in the drawing\, the problem boils down to finding an algorithm for a la beled abstract graph. To obtain these FPT algorithms we use different tool s including the sunflower lemma\, representative families for matroids\, a nd Courcelle's theorem. These techniques\, useful in many parameterized al gorithms\, will be briefly introduced during the talk.\n LOCATION:https://researchseminars.org/talk/CJCS/7/ END:VEVENT END:VCALENDAR