More Like this

1. A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs

   https://doi.org/10.1145/3519935.3519984  

   Chuzhoy, Julia; Tan, Zihan (June 2022, STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing)

   We consider the classical Minimum Crossing Number problem: given an n-vertex graph G, compute a drawing of G in the plane, while minimizing the number of crossings between the images of its edges. This is a fundamental and extensively studied problem, whose approximability status is widely open. In all currently known approximation algorithms, the approximation factor depends polynomially on Δ – the maximum vertex degree in G. The best current approximation algorithm achieves an O(n1/2−· (Δ·logn))-approximation, for a small fixed constant є, while the best negative result is APX-hardness, leaving a large gap in our understanding of this basic problem. In this paper we design a randomized O(2O((logn)7/8loglogn)·(Δ))-approximation algorithm for Minimum Crossing Number. This is the first approximation algorithm for the problem that achieves a subpolynomial in n approximation factor (albeit only in graphs whose maximum vertex degree is subpolynomial in n). In order to achieve this approximation factor, we design a new algorithm for a closely related problem called Crossing Number with Rotation System, in which, for every vertex v∈ V(G), the circular ordering, in which the images of the edges incident to v must enter the image of v in the drawing is fixed as part of input. Combining this result with the recent reduction of [Chuzhoy, Mahabadi, Tan ’20] immediately yields the improved approximation algorithm for Minimum Crossing Number. 

   more » « less
2. Characterization of T-Circles and Their Formation Reveal Similarities to Agrobacterium T-DNA Integration Patterns

   https://doi.org/10.3389/fpls.2022.849930  

   Singer, Kamy; Lee, Lan-Ying; Yuan, Jing; Gelvin, Stanton B. (May 2022, Frontiers in Plant Science)

   Agrobacterium transfers T-DNA to plants where it may integrate into the genome. Non-homologous end-joining (NHEJ) has been invoked as the mechanism of T-DNA integration, but the role of various NHEJ proteins remains controversial. Genetic evidence for the role of NHEJ in T-DNA integration has yielded conflicting results. We propose to investigate the formation of T-circles as a proxy for understanding T-DNA integration. T-circles are circular double-strand T-DNA molecules, joined at their left (LB) and right (RB) border regions, formed in plants. We characterized LB-RB junction regions from hundreds of T-circles formed in Nicotiana benthamiana or Arabidopsis thaliana . These junctions resembled T-DNA/plant DNA junctions found in integrated T-DNA: Among complex T-circles composed of multiple T-DNA molecules, RB-RB/LB-LB junctions predominated over RB-LB junctions; deletions at the LB were more frequent and extensive than those at the RB; microhomology was frequently used at junction sites; and filler DNA, from the plant genome or various Agrobacterium replicons, was often present between the borders. Ku80 was not required for efficient T-circle formation, and a VirD2 ω mutation affected T-circle formation and T-DNA integration similarly. We suggest that investigating the formation of T-circles may serve as a surrogate for understanding T-DNA integration. 

   more » « less
3. Local-global principles in circle packings

   https://doi.org/10.1112/S0010437X19007139  

   Fuchs, Elena; Stange, Katherine E.; Zhang, Xin (June 2019, Compositio Mathematica)

   We generalize work by Bourgain and Kontorovich [ On the local-global conjecture for integral Apollonian gaskets , Invent. Math. 196 (2014), 589–650] and Zhang [ On the local-global principle for integral Apollonian 3-circle packings , J. Reine Angew. Math. 737 , (2018), 71–110], proving an almost local-to-global property for the curvatures of certain circle packings, to a large class of Kleinian groups. Specifically, we associate in a natural way an infinite family of integral packings of circles to any Kleinian group $${\mathcal{A}}\leqslant \text{PSL}_{2}(K)$$ satisfying certain conditions, where $$K$$ is an imaginary quadratic field, and show that the curvatures of the circles in any such packing satisfy an almost local-to-global principle. A key ingredient in the proof is that $${\mathcal{A}}$$ possesses a spectral gap property, which we prove for any infinite-covolume, geometrically finite, Zariski dense Kleinian group in $$\operatorname{PSL}_{2}({\mathcal{O}}_{K})$$ containing a Zariski dense subgroup of $$\operatorname{PSL}_{2}(\mathbb{Z})$$ . 

   more » « less
4. Lombardi drawings of knots and links

   https://doi.org/10.1007/978-3-319-73915-1_10  

   Kindermann, P; Kobourov, S; Loeffler, M; Noellenburg, M; Schulz, A.; Vogtenhuber, B (January 2019, Journal of computational geometry)

   Knot and link diagrams are projections of one or more 3-dimensional simple closed curves into lR2, such that no more than two points project to the same point in lR2. These diagrams are drawings of 4-regular plane multigraphs. Knots are typically smooth curves in lR3, so their projections should be smooth curves in lR2 with good continuity and large crossing angles: exactly the properties of Lombardi graph drawings (defned by circular-arc edges and perfect angular resolution). We show that several knots do not allow crossing-minimal plane Lombardi drawings. On the other hand, we identify a large class of 4-regular plane multigraphs that do have plane Lombardi drawings. We then study two relaxations of Lombardi drawings and show that every knot admits a crossing-minimal plane 2-Lombardi drawing (where edges are composed of two circular arcs). Further, every knot is near-Lombardi, that is, it can be drawn as a plane Lombardi drawing when relaxing the angular resolution requirement by an arbitrary small angular offset ε, while maintaining a 180◦ angle between opposite edges. 

   more » « less
5. TEAM ADVANCE: Facilitated Peer Mentoring Circles Supporting Early Career Faculty

   Malloy, Erin; Foland, Joanna H. (December 2022, The chronicle of mentoring coaching)

   Though mentoring is associated with faculty productivity, career success, and satisfaction, barriers to effective mentoring such as time and resources persist. At UNC-Chapel Hill, mentoring climate surveys revealed uneven access to mentoring, with majority of faculty securing mentors on their own. Targeting Equity in Access to Mentoring (TEAM) ADVANCE (NSF Award#1760187) launched a facilitated peer mentoring circles program in fall 2019 to provide support for early career faculty in itsmultilevel intervention. TEAM ADVANCE Peer Mentoring Circles provide a semi-structured, facilitated peer mentoring model. Open to all early career faculty, each circle supports up to 6 mentees, facilitated by 2 senior faculty. A goals/values survey enabled formation of groups that include tenure-track and fixed-term faculty from a variety of disciplines. Circles meet monthly. Facilitators debrief between circles meetings. A concurrent professional development workshop series provides resources and topics for circle discussions. Circles also address individual and shared goals. A total of 168 faculty participated in the program over 3 academic years. Qualitative analysis of focus group data and open-ended responses on mentoring climate surveys from program participants revealed themes of safe spaces for conversations, access to senior faculty, access to career development resources, and networking with peers/similar social identities. Mentoring Climate Survey data from all faculty respondents indicated an increase in satisfaction with peer mentoring from fall 2019 to spring 2020, statistically significant for women (p < 0.05). The TEAM ADVANCE Peer Mentoring Circles program shows promise and scalability in supporting early career faculty across a wide range of social identities. Senior mentor-facilitators were appreciated. The semi-structured approach with access to workshops/content on professional development topics (e.g., negotiation, promotion/tenure, annual reviews) provides a base for Circles conversations to unfold to directly support peer mentees. The has been delivered in-person and virtually. Administrative support is the primary cost. 

   more » « less