A fixed-parameter algorithm for the minimum Manhattan network problem

Abstract

A Manhattan network for a finite set P of points in the plane is a geometric graph such that its vertex set contains P, its edges are axis-parallel and non-crossing and, for any two points p and q in P, there exists a path in the network connecting p and q whose length equals the l₁-distance between p and q.

The problem of computing a Manhattan network of minimum total edge length for a given point set P has recently been shown to be NP-hard. In this note, using as the parameter the minimum number h of horizontal straight lines that contain the points in P, we present a fixed-parameter algorithm for this problem running in O^*(2^14h) time and note that, under the exponential time hypothesis for 3-SAT, a run time that is subexponential in h is impossible.