Bounded-degree graphs have arbitrarily large geometric thickness

Abstract

The geometric thickness of a graph G is the minimum integer k such that there is a straight line drawing of G with its edge set partitioned into k plane subgraphs. We prove that there exists regular graphs of bounded degree with arbitrarily large geometric thickness.

Analogous results concerning graph drawings with few edge slopes are also presented.

Keywords

• Bounded-degree
• graphs
• arbitrarily
• large
• geometric
• thickness