No prior experience with this feature or scale, but Graphviz can embed images in the graph nodes it lays out. Write a script that converts your graph into a corresponding DOT (the input language for graphviz) file and places the images in the file system, then invoke graphviz.
Graphviz should handle that scale, and is quite flexible (raster graphics, svg, pdf all work, several layout engines to choose from).
We used to print a lot of posters for meetings. Many print shops have large format "plotters" that print to rolls of paper. Ink-jet and dye-sub are cheaper (dye-sub is the cheapest). The trick is rasterizing. The file can get rasterized by you, the technician, or the actual hardware. Doing it yourself or working with the tech is better than leaving it up to the hardware.
You should be able to use inkscape to convert to .pdf at a decent resolution.
Try a smaller tree first, to make sure the resolution is acceptable and the results are good.
Any architectural firm will be able to print it. They've got very large form printers for plans. There are also companies that do speciality printing because not every architect has the equipment. My mom's an architect and her old blue print machine used ammonia and smelled terrible. Nowadays, they don't smell so bad.