Sachverhalt: A. A._ ist Eigentümer der unüberbauten Parzelle Nr. 1624 in Heiden und der diese erschliessenden Strassenparzelle Nr. 1588 (Sonnenbergstrasse). Die Grundstücke sind Teil der Wohnzone W2a im Gebiet Sonnenberg. Am 9. Juni 2006 stellte A._ bei der Gemeinde Heiden das Begehren, die Sonnenbergstrasse sei in westliche Richtung zu verlängern, und zwar ab dem künftigen Wendeplatz über die benachbarten Grundstücke Nrn. 810 und 1855, die B._ gehören. Der Gemeinderat Heiden lehnte dieses Begehren mit Entscheid vom 24. Oktober 2006 ab. Am 2. Februar 2007 lehnte er in der gleichen Sache auch ein Wiedererwägungsbegehren von A._ ab. Gegen den Wiedererwägungsentscheid erhob A._ Rekurs beim kantonalen Departement für Bau und Umwelt. Er machte im Wesentlichen geltend, die neue Strassenverbindung sei nötig, weil sonst die künftigen Bewohner der Parzellen-Nrn. 1603, 1604, 1623 und 1624 einen fünf- bis zehnmal längeren Weg in die Langmoosstrasse in Kauf zu nehmen hätten. Durch die direkte Verbindung in die Sonnhalden- und Langmoostrasse könne mancher Fahrkilometer eingespart werden und gleichzeitig könne das östlich davon liegende Quartier (Sonnenberg) vom entsprechenden Durchgangsverkehr entlastet werden. Dies sei aus umweltschutz- und immissionsrechtlichen Gründen sachgerecht, weshalb sich daraus auch die Notwendigkeit dieser Erschliessungsvariante im Sinne von Art. 57 des kantonalen Baugesetzes vom 12. Mai 2003 (BauG/AR, bGS 721.1) ergebe. Das Departement für Bau und Umwelt wies den Rekurs am 9. Juli 2007 ab. Es begründete dies insbesondere damit, dass die im Jahre 1985 vom Regierungsrat mit dem Quartierplan Sonnenberg genehmigte Erschliessung der Parzellen Nrn. 1603, 1604, 1623 und 1624 einzig von der Sonnenbergstrasse her (mit Wendehammer) eine ausreichende Erschliessung darstelle. Damit könne, im Unterschied zur beantragten Verbindung in die Sonnhaldenstrasse, eine übermässige Erschliessung vermieden werden. Gegen den Rekursentscheid des Departements für Bau und Umwelt gelangte A._ am 13. August 2007 an das Verwaltungsgericht des Kantons Appenzell A.Rh. Er beantragte neben der Aufhebung der vorinstanzlichen Entscheide, der Gemeinderat Heiden sei anzuweisen, die Weiterführung der Sonnenbergstrasse in die Sonnhaldenstrasse in sein Erschliessungsprogramm aufzunehmen und den dafür erforderlichen Flächenbedarf mit den gegebenen planerischen Mitteln sicherzustellen. Nach einem Augenschein wies das Verwaltungsgericht die Beschwerde mit Urteil vom 27. August 2008 ab. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 13. Mai 2009 beantragt A._ die Aufhebung des Urteils des Verwaltungsgerichts vom 27. August 2008 sowie der unterinstanzlichen Entscheide des Departements für Bau und Umwelt und des Gemeinderats Heiden. Weiter verlangt er, der Gemeinderat sei anzuweisen, die Weiterführung der Sonnenbergstrasse in die Sonnhaldenstrasse in sein Erschliessungsprogramm aufzunehmen und den dafür erforderlichen Flächenbedarf mit den gegebenen planerischen Mitteln sicherzustellen. Er rügt insbesondere eine offensichtlich unrichtige Feststellung des Sachverhalts, die Verletzung von Art. 29 der Kantonsverfassung (SR 131.224.1), die Verletzung von Bundesrecht, namentlich von Art. 1 Abs. 2 lit. a und Art. 3 Abs. 2 lit. c-d und Abs. 3 lit. b RPG (SR 700) sowie der Art. 1 und 11 USG (SR 814.01). Zudem macht er Ermessensmissbrauch und eine Verletzung des Willkürverbots (Art. 9 BV) geltend. Das Verwaltungsgericht, das Departement für Bau und Umwelt sowie die Gemeinde Heiden beantragen die Abweisung der Beschwerde. B._ stellt den Antrag, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Der Beschwerdeführer hält in einer weiteren Eingabe an seinen Rechtsbegehren fest.