Thickness and antithickness of graphs

Vida Dujmović, David R. Wood

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.

Full Text:

PDF


DOI: http://dx.doi.org/10.20382/jocg.v9i1a12

ISSN: 1920-180X