I am on CentOS 5.5 compiling gnuplot 4.4.2.
Running ./configure completes without error. Running 'make' results in the following linker error:
gcc -g -O2 -o bf_test bf_test.o binary.o alloc.o -lreadline -lreadline -lreadline -lreadline -lm -L/lib64 -lz -lpangocairo-1.0 -lpango-1.0 -lcairo -lgobject-2.0 -lgmodule-2.0 -ldl -lglib-2.0
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/libreadline.so: undefined reference to `PC'
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/libreadline.so: undefined reference to `tgetflag'
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/libreadline.so: undefined reference to `tgetent'
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/libreadline.so: undefined reference to `UP'
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/libreadline.so: undefined reference to `tputs'
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/libreadline.so: undefined reference to `tgoto'
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/libreadline.so: undefined reference to `tgetnum'
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/libreadline.so: undefined reference to `BC'
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/libreadline.so: undefined reference to `tgetstr'
collect2: ld returned 1 exit status
I have the packages readline-devel and ncurses-devel installed. In order to compile I had to manually define the environment variable 'LIBS=-lncurses' before running configure.
This sounds to me like a CentOS packaging error. Gnuplot's configure script pulls the library dependencies from pkgconfig. Your libreadline-devel package should have installed a file /usr/lib/pkgconfig/readline.pc that specifies -lncurses as a dependency. If it did not do so, I think you should report this to Redhat and/or CentOS. (FWIW, the libreadline rpm is defective in this regard on current Mandriva as well.)
See for example: http://fr2.rpmfind.net/linux/OpenPKG/sources/SRC/readline/readline.spec