  Given a set $P$ of $n$ points with their pairwise distances, the traveling
salesman problem (TSP) asks for a shortest tour that visits each point exactly
once. A TSP instance is rectilinear when the points lie in the plane and the
distance considered between two points is the $l_1$ distance. In this paper, a
fixed-parameter algorithm for the Rectilinear TSP is presented and relies on
techniques for solving TSP on bounded-treewidth graphs. It proves that the
problem can be solved in $O\left(nh7^h\right)$ where $h \leq n$ denotes the
number of horizontal lines containing the points of $P$. The same technique can
be directly applied to the problem of finding a shortest rectilinear Steiner
tree that interconnects the points of $P$ providing a $O\left(nh5^h\right)$
time complexity. Both bounds improve over the best time bounds known for these
problems.

Data Structures and Algorithms;Computational Geometry;Discrete Mathematics