Bounds for generalized thrackles
A thrackle (or a generalized thrackle) is a drawing of a graph in which each pair of edges meet precisely once (or an odd number of times, respectively). For a graph with \(n\) vertices and \(m\) edges it is shown that \(m\leq 3(n-1)/2\) for thrackles in a plane, while \(m\leq 2n-2\) for generalized thrackles in a plane; this improves known results by Lovász, Pach and Szegedy. The paper also examines thrackles on closed surfaces, with the following main result: A bipartite graph can be drawn as a generalized thrackle on a closed connected orientable surface if and only if the graph can be embedded in that surface.
- Generalized thrackle drawings of non-bipartite graphs
- On edges crossing few other edges in simple topological complete graphs
- Generalized thrackles and geometric graphs in \({\mathbb{R}}^3\) with no pair of strongly avoiding edges
- Removing even crossings on surfaces
- Thrackles: an improved upper bound
- Which crossing number is it anyway?
- The \(\mathbb{Z}_2\)-genus of Kuratowski minors
- On the edge-vertex ratio of maximal thrackles
- On grids in topological graphs
- On embedding a graph in the grid with the maximum number of bends and other bad features
- Unified Hanani-Tutte theorem
- On the bounds of Conway's thrackles
- Great-circle spherical thrackles
- On the strong Hanani-Tutte theorem
- A new upper bound for Conway's thrackles
- Hanani-Tutte for radial planarity. II
- Bounded Embeddings of Graphs in the Plane
- Towards the Hanani-Tutte theorem for clustered graphs
- A direct proof of the strong Hanani-Tutte theorem on the projective plane
- Hanani-Tutte for Radial Planarity II
- Hanani-Tutte and monotone drawings
- Removing Even Crossings on Surfaces
- Thrackles: an improved upper bound
- Tangled thrackles
- The chromatic number of the convex segment disjointness graph
- The degenerate crossing number and higher-genus embeddings
- scientific article; zbMATH DE number 7559239 (Why is no real title available?)
- The $\mathbb{Z}_2$-genus of Kuratowski minors
- Thrackles containing a standard musquash
- A computational approach to Conway's thrackle conjecture
- On the optimality of the Arf invariant formula for graph polynomials
- Outerplanar thrackles
- Thrackles, superthrackles and the Hanani-Tutte theorem
- Convex hull thrackles
- A structure theorem for pseudo-segments and its applications
- On the number of digons in arrangements of pairwise intersecting circles
- A structure theorem for pseudosegments and its applications
- Strong Hanani-Tutte for the torus
- The maximum number of digons formed by pairwise intersecting pseudocircles
- Unavoidable patterns and plane paths in dense topological graphs
- Removing even crossings
- Clustered planarity testing revisited
- Pfaffian graphs, \(T\)-joins and crossing numbers
- Geometric graphs with no two parallel edges
This page was built for publication: Bounds for generalized thrackles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1971504)
