Orthogonal graph drawing with inflexible edges
Abstract We consider the problem of creating plane orthogonal drawings of 4 planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function assigning to each edge e a natural number flex e its flexibility. The problem FlexDraw asks whether there exists an orthogonal drawing such that each edge e has at most flex e bends. It is known that FlexDraw is NP hard if flex e 0 for every edge e [1] On the other hand, FlexDraw can be solved efficiently if flex e 1 [2] and is trivial if flex e 2 [3] for every edge e. To close the gap between the NP hardness for flex e 0 and the efficient algorithm for flex e 1 we investigate the computational complexity of FlexDraw in case only few edges are inflexible (i.e. have flexibility 0) We show that for any e 0 FlexDraw is NP complete for instances with O n e inflexible edges with pairwise distance O n 1 e (including the case where they induce a matching) where n denotes the number of vertices in the graph. On the other hand, we give an FPT algorithm with running time O 2 k n T flow n where T flow n is the time necessary to compute a maximum flow in a planar flow network with multiple sources and sinks, and k is the number of inflexible edges having at least one endpoint of degree 4.
Comput. Geom.