Abstract
This paper studies questions about duality between crossings and non-crossings in graph drawings via the notions of thickness and antithickness. The thickness of a graph G is the minimum integer k such that in some drawing of G, the edges can be partitioned into k noncrossing subgraphs. The antithickness of a graph G is the minimum integer k such that in some drawing of G, the edges can be partitioned into k thrackles, where a thrackle is a set of edges, each pair of which intersect exactly once. So thickness is a measure of how close a graph is to being planar, whereas antithickness is a measure of how close a graph is to being a thrackle. This paper explores the relationship between the thickness and antithickness of a graph, under various graph drawing models, with an emphasis on extremal questions.
Original language | English |
---|---|
Pages (from-to) | 356-386 |
Number of pages | 31 |
Journal | Journal of Computational Geometry |
Volume | 19 |
Issue number | 1 |
DOIs | |
Publication status | Published - 2018 |