Sounded like an interesting script, so I just wrote it in about a half hour. You're welcome to sell it if you want... (also, there's probably a default recursion limit of 100; unroll the recursion in walkpid to go farther) Collect logs with 'strace -o pids.log -e trace=process -f [specify your process here]', run with 'perl printpids.pl < pids.log'

  #!/usr/bin/perl -w
  $|=1;
  use strict;
  my (%pidmap, @order);
  while ( <> ) {
      chomp;
      if ( /^(\d+)\s+(\w+)(.*)$/ ) {
          my ($pid, $syscall, $args) = ($1, $2, $3);
          if ( $syscall =~ /(^clone$|fork$)/ and $args =~ / = (\d+)$/ and $1 > 0 ) {
              my $clonepid = $1;
              $pidmap{$clonepid} = { -parent => $pid };
              push(@order, $clonepid);
          }
          elsif ( $syscall =~ /^exec/ and $args =~ / = (\d+)$/ and $1 == 0 ) {
              my $exec = $args;
              @order = ($pid) if !@order;
              $exec =~ s/^\("([^"]+?)",.*$/$1/g;
              push( @{ $pidmap{$pid}->{-exec} } , $exec );
          }
      }
  }
  foreach my $pid ( @order ) {
      my $spaces = walkpid($pid);
      print "    " x $spaces . join("\n" . ("    " x $spaces), map { $_ . " ($pid)" } @{ $pidmap{$pid}->{-exec} } ) . "\n";
  }
  sub walkpid {
      my $pid = shift;
      my $c = shift || 0;
      if ( exists $pidmap{$pid}->{-parent} ) {
          return walkpid($pidmap{$pid}->{-parent}, $c+1);
      }
      return($pid, $c);
  }

Wow that's amazing! Can I have strace launch the program? Or does it already have to be running?

you can, last strace argument can be a command you want to strace

Valgrind's callgrind tool will profile all calls a program makes. You can them feed the output to kcachegrind (or qcachegrind for the Qt version) which will nicely visualize the profiling run.