  For a graph $G=(V,E)$, a subset $D$ of vertex set $V$, is a dominating set of
$G$ if every vertex not in $D$ is adjacent to atleast one vertex of $D$. A
dominating set $D$ of a graph $G$ with no isolated vertices is called a paired
dominating set (PD-set), if $G[D]$, the subgraph induced by $D$ in $G$ has a
perfect matching. The Min-PD problem requires to compute a PD-set of minimum
cardinality. The decision version of the Min-PD problem remains NP-complete
even when $G$ belongs to restricted graph classes such as bipartite graphs,
chordal graphs etc. On the positive side, the problem is efficiently solvable
for many graph classes including intervals graphs, strongly chordal graphs,
permutation graphs etc. In this paper, we study the complexity of the problem
in AT-free graphs and planar graph. The class of AT-free graphs contains
cocomparability graphs, permutation graphs, trapezoid graphs, and interval
graphs as subclasses. We propose a polynomial-time algorithm to compute a
minimum PD-set in AT-free graphs. In addition, we also present a linear-time
$2$-approximation algorithm for the problem in AT-free graphs. Further, we
prove that the decision version of the problem is NP-complete for planar
graphs, which answers an open question asked by Lin et al. (in Theor. Comput.
Sci., $591 (2015): 99-105$ and Algorithmica, $ 82 (2020) :2809-2840$).
