A fixed-parameter algorithm for the minimum Manhattan network problem

Christian Knauer, Andreas Spillner


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 andq in P, there exists a path in the network connecting p and whose length equals the l1-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*(214h) time and note that, under the exponential time hypothesis for 3-SAT, a run time that is subexponential in h is impossible.

Full Text:


DOI: http://dx.doi.org/10.20382/jocg.v2i1a10

ISSN: 1920-180X