diff --git a/go/git/repograph/graph.go b/go/git/repograph/graph.go
index 0238141..7d70ed5 100644
--- a/go/git/repograph/graph.go
+++ b/go/git/repograph/graph.go
@@ -14,7 +14,9 @@
 
 	"go.skia.org/infra/go/git"
 	"go.skia.org/infra/go/metrics2"
+	"go.skia.org/infra/go/skerr"
 	"go.skia.org/infra/go/sklog"
+	"go.skia.org/infra/go/util"
 	"go.skia.org/infra/go/vcsinfo"
 )
 
@@ -26,12 +28,6 @@
 type Commit struct {
 	*vcsinfo.LongCommit
 	parents []*Commit
-
-	// HistoryLen is the number of commits in the longest line of history
-	// reachable from this Commit. It is only used during Recurse as an
-	// estimate of the number of commits which might be visited, to prevent
-	// excessive resizing of the visited map.
-	HistoryLen int
 }
 
 // Parents returns the parents of this commit.
@@ -52,8 +48,11 @@
 // 	sklog.Info(c.Hash)
 // 	return nil
 // })
+//
+// If the passed-in function returns no errors other than ErrStopRecursing,
+// Recurse() will never return an error.
 func (c *Commit) Recurse(f func(*Commit) error) error {
-	return c.recurse(f, make(map[*Commit]bool, c.HistoryLen))
+	return c.recurse(f, make(map[*Commit]bool, c.Index+1))
 }
 
 // recurse is a helper function used by Recurse.
@@ -93,10 +92,28 @@
 	return nil
 }
 
+// RecurseFirstParent is like Recurse, but it only follows the first parent of
+// each commit. Like Recurse, if the passed-in function returns no errors other
+// than ErrStopRecursing, RecurseFirstParent() will never return an error.
+func (c *Commit) RecurseFirstParent(f func(*Commit) error) error {
+	for {
+		if err := f(c); err == ErrStopRecursing {
+			return nil
+		} else if err != nil {
+			return err
+		}
+		if len(c.parents) == 0 {
+			return nil
+		} else {
+			c = c.parents[0]
+		}
+	}
+}
+
 // AllCommits returns the hashes of all commits reachable from this Commit, in
 // reverse topological order.
 func (c *Commit) AllCommits() ([]string, error) {
-	commits := make(map[*Commit]bool, c.HistoryLen)
+	commits := make(map[*Commit]bool, c.Index+1)
 	if err := c.recurse(func(c *Commit) error {
 		return nil
 	}, commits); err != nil {
@@ -162,7 +179,8 @@
 	// Update the local view of the repo.
 	Update(context.Context) error
 
-	// Return the details for the given commit.
+	// Return the details for the given commit. The Graph takes ownership
+	// of the returned LongCommit and may modify it.
 	Details(context.Context, string) (*vcsinfo.LongCommit, error)
 
 	// Return the branch heads, as of the last call to Update().
@@ -179,8 +197,9 @@
 	commits  map[string]*Commit
 	graphMtx sync.RWMutex
 
-	updateMtx sync.Mutex
-	repoImpl  RepoImpl
+	updateMtx     sync.Mutex
+	repoImpl      RepoImpl
+	trackBranches bool
 }
 
 // NewLocalGraph returns a Graph instance, creating a git.Repo from the repoUrl
@@ -216,11 +235,50 @@
 	return len(r.commits)
 }
 
+// EnableBranchTracking enables tracking of commit membership in branches. A
+// commit is considered a member of a branch if and only if it is reachable by
+// tracing the *first parent* lineage backward from the branch head. Notably,
+// this will result in different branch membership than would be obtained by
+// `git branch --all --list --contains <hash` as is used elsewhere. This process
+// is somewhat expensive and is thus not enabled by default.
+func (r *Graph) EnableBranchTracking() {
+	r.updateMtx.Lock()
+	defer r.updateMtx.Unlock()
+	r.graphMtx.Lock()
+	defer r.graphMtx.Unlock()
+	r.trackBranches = true
+	r.updateBranchInfo()
+}
+
+// updateBranchInfo updates the membership of all commits in all branches. The
+// caller must hold r.updateMtx AND r.graphMtx.
+func (r *Graph) updateBranchInfo() {
+	// TODO(borenet): We have to obtain this information from scratch when
+	// EnableBranchTracking() is called, but we should be able to update it
+	// incrementally in updateFrom() in the common case. It seemed that
+	// there were enough edge cases that updateFrom() would become
+	// significantly more complicated, so I did not attempt that.
+	membership := make(map[*Commit]util.StringSet, len(r.commits))
+	for _, branch := range r.branches {
+		_ = r.commits[branch.Head].RecurseFirstParent(func(c *Commit) error {
+			m := membership[c]
+			if m == nil {
+				m = util.NewStringSet()
+				membership[c] = m
+			}
+			m[branch.Name] = true
+			return nil
+		})
+	}
+	for _, c := range r.commits {
+		c.Branches = membership[c]
+	}
+}
+
 // addCommit adds the given commit to the Graph. Requires that the commit's
 // parents are already in the Graph. Assumes that the caller holds r.graphMtx.
 func (r *Graph) addCommit(lc *vcsinfo.LongCommit) error {
 	defer metrics2.FuncTimer().Stop()
-	maxParentHistoryLen := 0
 	var parents []*Commit
 	if len(lc.Parents) > 0 {
 		for _, h := range lc.Parents {
@@ -232,8 +290,8 @@
 				return fmt.Errorf("repograph.Graph: Could not find parent commit %q", h)
 			}
 			parents = append(parents, p)
-			if p.HistoryLen > maxParentHistoryLen {
-				maxParentHistoryLen = p.HistoryLen
+			if lc.Index == 0 {
+				lc.Index = p.Index + 1
 			}
 		}
 	}
@@ -241,7 +299,6 @@
 	c := &Commit{
 		LongCommit: lc,
 		parents:    parents,
-		HistoryLen: maxParentHistoryLen + 1,
 	}
 	r.commits[c.Hash] = c
 	return nil
@@ -417,6 +474,9 @@
 	defer r.graphMtx.Unlock()
 	r.branches = newGraph.branches
 	r.commits = newGraph.commits
+	if r.trackBranches {
+		r.updateBranchInfo()
+	}
 	return added, removed, nil
 }
 
@@ -701,6 +761,39 @@
 	return rv
 }
 
+// LogLinear is equivalent to "git log --first-parent --ancestry-path from..to",
+// ie. it only returns commits which are on the direct path from A to B, and
+// only on the "main" branch. This is as opposed to "git log from..to" which
+// returns all commits which are ancestors of 'to' but not 'from'. The 'from'
+// commit may be the empty string, in which case all commits in the first-parent
+// line are returned.
+func (r *Graph) LogLinear(from, to string) ([]*Commit, error) {
+	fromCommit := r.Get(from)
+	if fromCommit == nil && from != "" {
+		return nil, skerr.Fmt("No such commit %q", from)
+	}
+	toCommit := r.Get(to)
+	if toCommit == nil {
+		return nil, skerr.Fmt("No such commit %q", to)
+	}
+	rv := []*Commit{}
+	found := false
+	_ = toCommit.RecurseFirstParent(func(c *Commit) error {
+		if c == fromCommit {
+			found = true
+			return ErrStopRecursing
+		}
+		rv = append(rv, c)
+		return nil
+	})
+	if !found && from != "" {
+		// If the "from" commit was not found, then there is no ancestry
+		// path from "from" to "to".
+		return nil, nil
+	}
+	return rv, nil
+}
+
 // IsAncestor returns true iff A is an ancestor of B, where A and B are either
 // commit hashes or branch names.
 func (r *Graph) IsAncestor(a, b string) (bool, error) {
@@ -818,6 +911,9 @@
 		newGraph := newGraphs[repoUrl]
 		r.branches = newGraph.branches
 		r.commits = newGraph.commits
+		if r.trackBranches {
+			r.updateBranchInfo()
+		}
 	}
 	return added, removed, nil
 }
diff --git a/go/git/repograph/local_test.go b/go/git/repograph/local_test.go
index 321f1bb..3a823a6 100644
--- a/go/git/repograph/local_test.go
+++ b/go/git/repograph/local_test.go
@@ -57,6 +57,13 @@
 	shared_tests.TestRecurseAllBranches(t, ctx, g, repo, ud)
 }
 
+func TestLogLinearRepo(t *testing.T) {
+	unittest.MediumTest(t)
+	ctx, g, repo, ud, cleanup := setupRepo(t)
+	defer cleanup()
+	shared_tests.TestLogLinear(t, ctx, g, repo, ud)
+}
+
 func TestUpdateHistoryChangedRepo(t *testing.T) {
 	unittest.MediumTest(t)
 	ctx, g, repo, ud, cleanup := setupRepo(t)
@@ -77,3 +84,10 @@
 	defer cleanup()
 	shared_tests.TestRevList(t, ctx, g, repo, ud)
 }
+
+func TestBranchMembershipRepo(t *testing.T) {
+	unittest.MediumTest(t)
+	ctx, g, repo, ud, cleanup := setupRepo(t)
+	defer cleanup()
+	shared_tests.TestBranchMembership(t, ctx, g, repo, ud)
+}
diff --git a/go/git/repograph/shared_tests/shared_tests.go b/go/git/repograph/shared_tests/shared_tests.go
index f662c77..e4ee171 100644
--- a/go/git/repograph/shared_tests/shared_tests.go
+++ b/go/git/repograph/shared_tests/shared_tests.go
@@ -7,6 +7,7 @@
 	"os"
 	"path"
 	"sort"
+	"strings"
 
 	assert "github.com/stretchr/testify/require"
 	"go.skia.org/infra/go/deepequal"
@@ -214,6 +215,13 @@
 	assert.Equal(t, []*repograph.Commit(nil), c1.GetParents())
 	assert.Equal(t, []*repograph.Commit{c2}, c3.GetParents())
 
+	// Assert that each of the commits has the correct index.
+	assert.Equal(t, 0, c1.Index)
+	assert.Equal(t, 1, c2.Index)
+	assert.Equal(t, 2, c3.Index)
+	assert.Equal(t, 2, c4.Index)
+	assert.Equal(t, 3, c5.Index)
+
 	// Ensure that we can start in an empty dir and check out from scratch properly.
 	tmp2, err := ioutil.TempDir("", "")
 	assert.NoError(t, err)
@@ -358,6 +366,50 @@
 	assert.True(t, gotCommits[c2])
 }
 
+func TestLogLinear(t sktest.TestingT, ctx context.Context, g *git_testutils.GitBuilder, repo *repograph.Graph, rf RepoImplRefresher) {
+	commits := GitSetup(t, ctx, g, repo, rf)
+
+	c1 := commits[0]
+	c2 := commits[1]
+	c3 := commits[2]
+	c4 := commits[3]
+	c5 := commits[4]
+
+	gitdir := git.GitDir(g.Dir())
+	test := func(from, to string, checkAgainstGit bool, expect ...*repograph.Commit) {
+		if checkAgainstGit {
+			// Ensure that our expectations match actual git results.
+			cmd := []string{"--first-parent"}
+			if from == "" {
+				cmd = append(cmd, to)
+			} else {
+				cmd = append(cmd, "--ancestry-path", fmt.Sprintf("%s..%s", from, to))
+			}
+			hashes, err := gitdir.RevList(ctx, cmd...)
+			assert.NoError(t, err)
+			assert.Equal(t, len(hashes), len(expect))
+			for i, h := range hashes {
+				assert.Equal(t, h, expect[i].Hash)
+			}
+		}
+
+		// Ensure that we get the expected results from the Graph.
+		actual, err := repo.LogLinear(from, to)
+		assert.NoError(t, err)
+		deepequal.AssertDeepEqual(t, expect, actual)
+	}
+
+	// Get the full linear history from c5.
+	test("", c5.Hash, true, c5, c4, c2, c1)
+	// Get the linear history from c1 to c5. Like "git log", we don't
+	// include the "from" commit in the results.
+	test(c1.Hash, c5.Hash, true, c5, c4, c2)
+	// c3 is not reachable via first-parents from c5. For some reason, git
+	// actually returns c5.Hash, even though c5 has c4 as its first parent.
+	// Ignore the check against git in this case.
+	test(c3.Hash, c5.Hash, false)
+}
+
 func TestUpdateHistoryChanged(t sktest.TestingT, ctx context.Context, g *git_testutils.GitBuilder, repo *repograph.Graph, rf RepoImplRefresher) {
 	commits := GitSetup(t, ctx, g, repo, rf)
 
@@ -671,3 +723,87 @@
 	check(commits[2], commits[4], commits[3:5])
 	check(commits[3], commits[4], []string{commits[2], commits[4]})
 }
+
+func TestBranchMembership(t sktest.TestingT, ctx context.Context, gb *git_testutils.GitBuilder, repo *repograph.Graph, rf RepoImplRefresher) {
+	commits := GitSetup(t, ctx, gb, repo, rf)
+	c1 := commits[0]
+	c2 := commits[1]
+	c3 := commits[2]
+	c4 := commits[3]
+	c5 := commits[4]
+	test := func(c *repograph.Commit, branches ...string) {
+		sklog.Errorf("%d: %s", c.Index, c.Hash)
+		sklog.Errorf("Expect:\n%s", strings.Join(branches, "\n"))
+		actualStr := ""
+		for branch := range c.Branches {
+			actualStr += branch + "\n"
+		}
+		sklog.Errorf("Actual:\n%s", actualStr)
+		assert.Equal(t, len(branches), len(c.Branches))
+		for _, b := range branches {
+			assert.True(t, c.Branches[b])
+		}
+	}
+
+	// Branches should be nil at first.
+	for _, c := range commits {
+		assert.Nil(t, c.Branches)
+	}
+
+	// Enable branch tracking. Ensure that all commits were updated with the
+	// correct branch membership.
+	repo.EnableBranchTracking()
+	test(c1, "master", "branch2")
+	test(c2, "master", "branch2")
+	test(c3, "branch2") // c3 is reachable from master, but not via first-parent.
+	test(c4, "master")
+	test(c5, "master")
+
+	// Ensure that subsequent calls to Update() cause the branch membership
+	// to be updated.
+	gb.CreateBranchTrackBranch(ctx, "b3", "master")
+	rf.Refresh()
+	assert.NoError(t, repo.Update(ctx))
+	test(c1, "master", "branch2", "b3")
+	test(c2, "master", "branch2", "b3")
+	test(c3, "branch2") // c3 is reachable from b3, but not via first-parent.
+	test(c4, "master", "b3")
+	test(c5, "master", "b3")
+
+	// Reset b3 to branch2.
+	gb.Reset(ctx, "--hard", "branch2")
+	rf.Refresh()
+	assert.NoError(t, repo.Update(ctx))
+	test(c1, "master", "branch2", "b3")
+	test(c2, "master", "branch2", "b3")
+	test(c3, "branch2", "b3")
+	test(c4, "master")
+	test(c5, "master")
+
+	// Delete b3. We should get the same results as before it was added.
+	gb.CheckoutBranch(ctx, "master")
+	gb.UpdateRef(ctx, "-d", "refs/heads/b3")
+	rf.Refresh()
+	assert.NoError(t, repo.Update(ctx))
+	test(c1, "master", "branch2")
+	test(c2, "master", "branch2")
+	test(c3, "branch2")
+	test(c4, "master")
+	test(c5, "master")
+
+	// Ensure that repograph.Map updates branch membership as well.
+	m := repograph.Map{"dummy": repo}
+	c6hash := gb.CommitGen(ctx, "blah")
+	c6details, err := git.GitDir(gb.Dir()).Details(ctx, c6hash)
+	assert.NoError(t, err)
+	rf.Refresh(c6details)
+	assert.NoError(t, m.Update(ctx))
+	c6 := repo.Get(c6hash)
+	assert.NotNil(t, c6)
+	test(c1, "master", "branch2")
+	test(c2, "master", "branch2")
+	test(c3, "branch2")
+	test(c4, "master")
+	test(c5, "master")
+	test(c6, "master")
+}
diff --git a/go/gitstore/bt_gitstore/repo_impl_test.go b/go/gitstore/bt_gitstore/repo_impl_test.go
index 50a695b..3494e18 100644
--- a/go/gitstore/bt_gitstore/repo_impl_test.go
+++ b/go/gitstore/bt_gitstore/repo_impl_test.go
@@ -119,6 +119,13 @@
 	repograph_shared_tests.TestRecurseAllBranches(t, ctx, g, repo, ud)
 }
 
+func TestLogLinearBTGitStore(t *testing.T) {
+	unittest.LargeTest(t)
+	ctx, g, repo, ud, cleanup := setupGitStore(t)
+	defer cleanup()
+	repograph_shared_tests.TestLogLinear(t, ctx, g, repo, ud)
+}
+
 func TestUpdateHistoryChangedBTGitStore(t *testing.T) {
 	unittest.LargeTest(t)
 	ctx, g, repo, ud, cleanup := setupGitStore(t)
@@ -139,3 +146,10 @@
 	defer cleanup()
 	repograph_shared_tests.TestRevList(t, ctx, g, repo, ud)
 }
+
+func TestBranchMembershipBTGitStore(t *testing.T) {
+	unittest.LargeTest(t)
+	ctx, g, repo, ud, cleanup := setupGitStore(t)
+	defer cleanup()
+	repograph_shared_tests.TestBranchMembership(t, ctx, g, repo, ud)
+}
diff --git a/go/gitstore/repo_impl_test.go b/go/gitstore/repo_impl_test.go
index 596dec1..2d1233f 100644
--- a/go/gitstore/repo_impl_test.go
+++ b/go/gitstore/repo_impl_test.go
@@ -166,6 +166,13 @@
 	repograph_shared_tests.TestRecurseAllBranches(t, ctx, g, repo, ud)
 }
 
+func TestLogLinearGitStore(t *testing.T) {
+	unittest.LargeTest(t)
+	ctx, g, repo, ud, cleanup := setupGitStore(t)
+	defer cleanup()
+	repograph_shared_tests.TestLogLinear(t, ctx, g, repo, ud)
+}
+
 func TestUpdateHistoryChangedGitStore(t *testing.T) {
 	unittest.LargeTest(t)
 	ctx, g, repo, ud, cleanup := setupGitStore(t)
@@ -186,3 +193,10 @@
 	defer cleanup()
 	repograph_shared_tests.TestRevList(t, ctx, g, repo, ud)
 }
+
+func TestBranchMembershipGitStore(t *testing.T) {
+	unittest.LargeTest(t)
+	ctx, g, repo, ud, cleanup := setupGitStore(t)
+	defer cleanup()
+	repograph_shared_tests.TestBranchMembership(t, ctx, g, repo, ud)
+}
diff --git a/go/vcsinfo/types.go b/go/vcsinfo/types.go
index 593ff23..857848e 100644
--- a/go/vcsinfo/types.go
+++ b/go/vcsinfo/types.go
@@ -16,9 +16,9 @@
 	MaxTime = time.Unix(9999999999, 0)
 )
 
-// IndexCommit is information about a commit that includes the offset from
-// the first commit in the repository. The first commit in the branch has Index 0.
-// Usually the indexing makes most sense the commits on a branch in first-parent order.
+// IndexCommit is information about a commit that includes the commit's index
+// in the linear ancestry path obtained by following each commit's first parent
+// backward in history. The first commit in a given branch has Index 0.
 type IndexCommit struct {
 	Hash      string
 	Index     int
@@ -35,10 +35,16 @@
 // LongCommit gives more detailed information about a commit.
 type LongCommit struct {
 	*ShortCommit
-	Parents   []string        `json:"parent"`
-	Body      string          `json:"body"`
-	Timestamp time.Time       `json:"timestamp"`
-	Branches  map[string]bool `json:"-"`
+	Parents   []string  `json:"parent"`
+	Body      string    `json:"body"`
+	Timestamp time.Time `json:"timestamp"`
+	// Index is this Commit's index in the linear ancestry path obtained by
+	// following each commit's first parent backward in history. The first
+	// commit in a given branch has Index 0. This field is not set by
+	// default.
+	Index int `json:"-"`
+	// Branches indicates which branches can reach this commit.
+	Branches map[string]bool `json:"-"`
 }
 
 func NewLongCommit() *LongCommit {