Group for Research in Decision Analysis

# Geometric Thickness Parameters of Graphs

## Vida Dujmovic – McGill University, 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.