2019/08/23 by Yoshio Okamoto, Okamoto, Yoshio, Alexander Ravsky +3 · 1 citation
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1908.08871
openalex publication_date 2019/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The 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. Then we establish the ∃ℝ-completeness (which implies the NP-hardness) of all variants. Finally, for cubic graphs, we prove lower and upper bounds on the new variants of the segment number, depending on the connectivity of the given graph.