2023/08/29 by Sabine Cornelsen, Cornelsen, Sabine, Giordano Da Lozzo +9 · 1 citation
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2308.15416
openalex publication_date 2023/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a straight-line drawing of a graph, a segment is a maximal set of edges that form a line segment. Given a planar graph G, the segment number of G is the minimum number of segments that can be achieved by any planar straight-line drawing of G. The line cover number of G is the minimum number of lines that support all the edges of a planar straight-line drawing of G. Computing the segment number or the line cover number of a planar graph is ∃ℝ-complete and, thus, NP-hard. We study the problem of computing the segment number from the perspective of parameterized complexity. We show that this problem is fixed-parameter tractable with respect to each of the following parameters: the vertex cover number, the segment number, and the line cover number. We also consider colored versions of the segment and the line cover number.