I have checked MP4 with following properties are supported on Toyota Altis 2013 dvd player.
Video codec: MPEG4
Resolution: 720 x 480
Bitrate: 2000 Kbps
Frame Rate: 25 FPS
Audio Codec: ACC
Bitrate: 125 Kbps
Channel: 2
Use any video conveter to convert in this format. I have used iSkySoft and Video Converter Ultimate.