Inserting edges into simple drawings

Abstract: Simple drawings of graphs are those in which each pair of edges share at most one point, either a common endpoint or a proper crossing. Given a simple drawing D of a graph G, in this talk we consider the problem of inserting a given set of missing edges (edges of the complement of G) into D such that the result is again a simple drawing. We show that it is NP-complete to decide whether one edge can be inserted into a simple drawing. On the positive side, we present a Fixed-Parameter Tractable (FPT) algorithm for this problem parameterized by the number of crossings that the edge to be inserted 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 working in the drawing, the problem boils down to finding an algorithm for a labeled abstract graph. To obtain these FPT algorithms we use different tools including the sunflower lemma, representative families for matroids, and Courcelle's theorem. These techniques, useful in many parameterized algorithms, will be briefly introduced during the talk.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456