BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Radoslav Fulek (UC San Diego) DTSTART:20220825T141500Z DTEND:20220825T160000Z DTSTAMP:20260422T065935Z UID:CJCS/78 DESCRIPTION:Title: At omic Embeddability\, Clustered Planarity\, and Thickenability\nby Rado slav Fulek (UC San Diego) as part of Copenhagen-Jerusalem Combinatorics Se minar\n\n\nAbstract\nThe planarity testing problem is the algorithmic prob lem of testing whether a given input graph is planar\, that is\, whether i t can be drawn in the plane without edge crossings. C-planarity was introd uced in 1995 by Feng\, Cohen\, and Eades as a generalization of graph plan arity\, in which the vertex set of the input graph is endowed with a hiera rchical clustering and we seek an embedding (edge crossing-free drawing) o f the graph in the plane that respects the clustering in a certain natural sense.\n\nThe problem of thickenability for simplicial complexes emerged in the topology of manifolds in the 1960s. A 2-dimensional simplicial comp lex is thickenable if it embeds in some orientable 3 dimensional manifold. \n\nWe study the atomic embeddability testing problem\, which is a common generalization of clustered planarity (c-planarity\, for short) and thicke nability testing\, and present a polynomial time algorithm for this proble m\, thereby giving the first polynomial time algorithm for c-planarity.\n\ nBefore our work\, it has been an open problem whether c-planarity can be tested efficiently\, despite relentless efforts. Recently\, Carmesin annou nced that thickenability can be tested in polynomial time. Our algorithm f or atomic embeddability combines ideas from Carmesin's work with algorithm ic tools previously developed for so-called weak embeddability testing.\n\ nJoint work with Csaba Tóth.\n LOCATION:https://researchseminars.org/talk/CJCS/78/ END:VEVENT END:VCALENDAR