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 there exists R-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.
Cornelsen, S., Da Lozzo, G., Grilli, L., Gupta, S., Kratochvíl, J., Wolff, A. (2023). The Parametrized Complexity of the Segment Number. In Graph Drawing and Network Visualization - 31st International Symposium, GD 2023 (pp.97-113). GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND : SPRINGER INTERNATIONAL PUBLISHING AG [10.1007/978-3-031-49275-4_7].
The Parametrized Complexity of the Segment Number
Da Lozzo, Giordano;
2023-01-01
Abstract
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 there exists R-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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
