dpkg: How to remove a package and all other packages which depend on it?

I tried to remove KDE from my system. When I run dpkg -r kdebase-bin, it says kdebase-data depends on it. So how can I remove all the packages related to KDE?

Usually one uses a higher-level utility instead of dpkg. You can use apt-get to remove a package and all its dependencies.

apt-get remove <package>

dpkg -r --force-depends  $pkg
apt-get install -f

Unlike apt-get, aptitude can recursively remove packages which were installed as dependencies, but which are no longer depended on when the requested removal happens. You have to have installed those packages with aptitude in order for this to work, though.

There are also tools like deborphan which can identify packages which may no longer be necessary on your system, even if you didn't use aptitude to install them. However, you have to supply it with a list of packages you do want on your system, but it's usually a quick job (there will be fewer packages it has to ask about than you might imagine).