diff --git a/src/console/grid/ArcanistGridColumn.php b/src/console/grid/ArcanistGridColumn.php
--- a/src/console/grid/ArcanistGridColumn.php
+++ b/src/console/grid/ArcanistGridColumn.php
@@ -6,6 +6,7 @@
   private $key;
   private $alignment = self::ALIGNMENT_LEFT;
   private $displayWidth;
+  private $minimumWidth;
 
   const ALIGNMENT_LEFT = 'align.left';
   const ALIGNMENT_CENTER = 'align.center';
@@ -38,4 +39,13 @@
     return $this->displayWidth;
   }
 
+  public function setMinimumWidth($minimum_width) {
+    $this->minimumWidth = $minimum_width;
+    return $this;
+  }
+
+  public function getMinimumWidth() {
+    return $this->minimumWidth;
+  }
+
 }
diff --git a/src/console/grid/ArcanistGridView.php b/src/console/grid/ArcanistGridView.php
--- a/src/console/grid/ArcanistGridView.php
+++ b/src/console/grid/ArcanistGridView.php
@@ -10,7 +10,7 @@
 
   public function setColumns(array $columns) {
     assert_instances_of($columns, 'ArcanistGridColumn');
-    $this->columns = $columns;
+    $this->columns = mpull($columns, null, 'getKey');
     return $this;
   }
 
@@ -56,27 +56,70 @@
     return tsprintf("%s\n", $rows);
   }
 
-  private function getDisplayWidth($key) {
-    if (!isset($this->displayWidths[$key])) {
-      $column = $this->getColumn($key);
+  private function getDisplayWidth($display_key) {
+    if (!isset($this->displayWidths[$display_key])) {
+      $flexible_columns = array();
 
-      $width = $column->getDisplayWidth();
-      if ($width === null) {
-        $width = 1;
-        foreach ($this->getRows() as $row) {
-          if (!$row->hasCell($key)) {
-            continue;
+      $columns = $this->getColumns();
+      foreach ($columns as $key => $column) {
+        $width = $column->getDisplayWidth();
+
+        if ($width === null) {
+          $width = 1;
+          foreach ($this->getRows() as $row) {
+            if (!$row->hasCell($key)) {
+              continue;
+            }
+
+            $cell = $row->getCell($key);
+            $width = max($width, $cell->getContentDisplayWidth());
           }
+        }
 
-          $cell = $row->getCell($key);
-          $width = max($width, $cell->getContentDisplayWidth());
+        if ($column->getMinimumWidth() !== null) {
+          $flexible_columns[] = $key;
         }
+
+        $this->displayWidths[$key] = $width;
       }
 
-      $this->displayWidths[$key] = $width;
+      $available_width = phutil_console_get_terminal_width();
+
+      // Adjust the available width to account for cell spacing.
+      $available_width -= (2 * (count($columns) - 1));
+
+      while (true) {
+        $total_width = array_sum($this->displayWidths);
+
+        if ($total_width <= $available_width) {
+          break;
+        }
+
+        if (!$flexible_columns) {
+          break;
+        }
+
+        // NOTE: This is very unsophisticated, and just shortcuts us to a
+        // reasonable result when only one column is flexible.
+
+        foreach ($flexible_columns as $flexible_key) {
+          $column = $columns[$flexible_key];
+
+          $need_width = ($total_width - $available_width);
+          $old_width = $this->displayWidths[$flexible_key];
+          $new_width = ($old_width - $need_width);
+
+          $new_width = max($new_width, $column->getMinimumWidth());
+
+          $this->displayWidths[$flexible_key] = $new_width;
+
+          $flexible_columns = array();
+          break;
+        }
+      }
     }
 
-    return $this->displayWidths[$key];
+    return $this->displayWidths[$display_key];
   }
 
   public function getColumn($key) {
@@ -241,7 +284,12 @@
     $src_width,
     $dst_width,
     $alignment) {
-    return $line;
+
+    $line = phutil_string_cast($line);
+
+    return id(new PhutilUTF8StringTruncator())
+      ->setMaximumGlyphs($dst_width)
+      ->truncateString($line);
   }
 
 }
diff --git a/src/ref/revision/ArcanistRevisionRef.php b/src/ref/revision/ArcanistRevisionRef.php
--- a/src/ref/revision/ArcanistRevisionRef.php
+++ b/src/ref/revision/ArcanistRevisionRef.php
@@ -89,6 +89,13 @@
     return 'D'.$this->getID();
   }
 
+  public function getStatusShortDisplayName() {
+    if ($this->isStatusNeedsReview()) {
+      return pht('Review');
+    }
+    return idxv($this->parameters, array('fields', 'status', 'name'));
+  }
+
   public function getStatusDisplayName() {
     return idxv($this->parameters, array('fields', 'status', 'name'));
   }
@@ -117,6 +124,11 @@
     return ($status === 'accepted');
   }
 
+  public function isStatusNeedsReview() {
+    $status = $this->getStatus();
+    return ($status === 'needs-review');
+  }
+
   public function getStatus() {
     return idxv($this->parameters, array('fields', 'status', 'value'));
   }
diff --git a/src/repository/graph/view/ArcanistCommitGraphSetView.php b/src/repository/graph/view/ArcanistCommitGraphSetView.php
--- a/src/repository/graph/view/ArcanistCommitGraphSetView.php
+++ b/src/repository/graph/view/ArcanistCommitGraphSetView.php
@@ -249,9 +249,8 @@
         substr($max->getCommitHash(), 0, 7));
     }
 
-    // TODO: Make this a function of terminal width?
-
-    $max_depth = 25;
+    $terminal_width = phutil_console_get_terminal_width();
+    $max_depth = (int)floor(3 + (max(0, $terminal_width - 72) / 6));
     if ($depth <= $max_depth) {
       $indent = str_repeat(' ', ($depth * 2));
     } else {
@@ -262,20 +261,29 @@
 
     $empty_indent = str_repeat(' ', strlen($indent));
 
+    $max_width = ($max_depth * 2) + 16;
+    $available_width = $max_width - (min($max_depth, $depth) * 2);
+
     $is_first = true;
     $cell = array();
     foreach ($items as $item) {
       $marker_ref = idx($item, 'marker');
 
       if ($marker_ref) {
+        $marker_name = $marker_ref->getName();
+
+        $marker_name = id(new PhutilUTF8StringTruncator())
+          ->setMaximumGlyphs($available_width)
+          ->truncateString($marker_name);
+
         if ($marker_ref->getIsActive()) {
           $label = tsprintf(
             '<bg:green>**%s**</bg>',
-            $marker_ref->getName());
+            $marker_name);
         } else {
           $label = tsprintf(
             '**%s**',
-            $marker_ref->getName());
+            $marker_name);
         }
       } else if ($is_first) {
         $label = $commit_label;
@@ -391,7 +399,11 @@
 
 
   private function drawRevisionStatus(ArcanistRevisionRef $revision_ref) {
-    $status = $revision_ref->getStatusDisplayName();
+    if (phutil_console_get_terminal_width() < 120) {
+      $status = $revision_ref->getStatusShortDisplayName();
+    } else {
+      $status = $revision_ref->getStatusDisplayName();
+    }
 
     $ansi_color = $revision_ref->getStatusANSIColor();
     if ($ansi_color) {
diff --git a/src/workflow/ArcanistMarkersWorkflow.php b/src/workflow/ArcanistMarkersWorkflow.php
--- a/src/workflow/ArcanistMarkersWorkflow.php
+++ b/src/workflow/ArcanistMarkersWorkflow.php
@@ -151,7 +151,8 @@
     $grid->newColumn('commits');
     $grid->newColumn('status');
     $grid->newColumn('revisions');
-    $grid->newColumn('messages');
+    $grid->newColumn('messages')
+      ->setMinimumWidth(12);
 
     foreach ($partition_lists as $row_lists) {
       foreach ($row_lists as $row_list) {