Groupe d’études et de recherche en analyse des décisions

Geometric Thickness Parameters of Graphs

Vida Dujmovic Université McGill, Canada

Partitions of the edge set of a graph into a small number of 'nice' subgraphs are in the mainstream of graph theory. For example, in a proper edge colouring, the subgraphs of the partition are matching. If each subgraph of a partition is required to be planar (respectively, a forest), then the minimum number of subgraphs in a partition of a graph \(G\) is the thickness (arboricity) of \(G\). These are classical graph parameters that have been studied since the early 1960s.

We study graph partitions with additional geometric properties. Namely, there is a drawing of the graph, and each subgraph in the partition is drawn without crossings. This type of drawing has applications in graph visualization (where each noncrossing subgraph is coloured by a distinct colour), and in multilayer VLSI (where each noncrossing subgraph corresponds to a set of wires that can be routed without crossings in a single layer). With no restriction on how the edges are drawn, the minimum number of noncrossing subgraphs, taken over all drawings of \(G\), is again the thickness of \(G\). By restricting the edges to be drawn straight, we obtain the geometric thickness of \(G\). By further restricting the vertices to be in convex position, we obtain book thickness of \(G\).

We study the relationship between these geometric graph parameters and treewidth. Treewidth, is a modern graph parameter that is particularly important in structural and algorithmic graph theory.

This is joint work with David R. Wood.