  A map graph is a graph admitting a representation in which vertices are
nations on a spherical map and edges are shared curve segments or points
between nations. We present an explicit fixed-parameter tractable algorithm for
recognizing map graphs parameterized by treewidth. The algorithm has time
complexity that is linear in the size of the graph and, if the input is a
yes-instance, it reports a certificate in the form of a so-called witness.
Furthermore, this result is developed within a more general algorithmic
framework that allows to test, for any $k$, if the input graph admits a $k$-map
(where at most $k$ nations meet at a common point) or a hole-free~$k$-map
(where each point of the sphere is covered by at least one nation). We point
out that, although bounding the treewidth of the input graph also bounds the
size of its largest clique, the latter alone does not seem to be a strong
enough structural limitation to obtain an efficient time complexity. In fact,
while the largest clique in a $k$-map graph is $\lfloor 3k/2 \rfloor$, the
recognition of $k$-map graphs is still open for any fixed $k \ge 5$.
