Fixed-Parameter Algorithms for Computing Bend-Restricted RAC Drawings of Graphs

Abstract

In a right-angle crossing (RAC) drawing of a graph, each edge is represented as a polyline and edge crossings must occur at an angle of exactly 90°, where the number of bends on such polylines is typically restricted in some way. While structural and topological properties of RAC drawings have been the focus of extensive research and particular attention has been paid to RAC drawings with at most 0, 1, 2 and 3 bends per edge, little was known about the boundaries of tractability for computing such drawings. In this paper, we initiate the study of bend-restricted RAC drawings from the viewpoint of parameterized complexity. In particular, we establish that computing a RAC drawing of an input graph G with at most b bends where each edge e has a prescribed upper-bound 0 <= β(e) <= 3 on the number of bends it can support (or determining that none exists) is:

fixed-parameter tractable parameterized by the feedback edge number of G, and

fixed-parameter tractable parameterized by plus the vertex cover number of G.