Variants of the Segment Number of a Graph

Understand

The \emph{segment number} of a planar graph is the smallest number of line segments whose union represents a crossing-free straight-line drawing of the given graph in the plane.

• The segment number is a measure for the visual complexity of a drawing; it has been studied extensively.
• In this paper, we study three variants of the segment number: for planar graphs, we consider crossing-free polyline drawings in 2D; for arbitrary graphs, we consider crossing-free straight-line drawings in 3D and straight-line drawings with crossings in 2D.
• We first construct an infinite family of planar graphs where the classical segment number is asymptotically twice as large as each of the new variants of the segment number.