On the Parameterized Complexity of Bend-Minimum Orthogonal Planarity

Computing planar orthogonal drawings with the minimum number of bends is one of the most relevant topics in Graph Drawing. The problem is known to be NP-hard, even when we want to test the existence of a rectilinear planar drawing, i.e., an orthogonal drawing without bends (Garg and Tamassia, 2001)....

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-09
Main Authors: Emilio Di Giacomo, Didimo, Walter, Liotta, Giuseppe, Montecchiani, Fabrizio, Ortali, Giacomo
Format: Article
Language:English
Subjects:
Apexes
Bends
Complexity
Parameterization
Parameters
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Computing planar orthogonal drawings with the minimum number of bends is one of the most relevant topics in Graph Drawing. The problem is known to be NP-hard, even when we want to test the existence of a rectilinear planar drawing, i.e., an orthogonal drawing without bends (Garg and Tamassia, 2001). From the parameterized complexity perspective, the problem is fixed-parameter tractable when parameterized by the sum of three parameters: the number of bends, the number of vertices of degree at most two, and the treewidth of the input graph (Di Giacomo et al., 2022). We improve this last result by showing that the problem remains fixed-parameter tractable when parameterized only by the number of vertices of degree at most two plus the number of bends. As a consequence, rectilinear planarity testing lies in \FPT~parameterized by the number of vertices of degree at most two.
ISSN:2331-8422