We study how to evaluate basic graph patterns (BGPs) over temporal labeled graphs--where each edge is associated with an interval of temporal validity--in a worst-case-optimal manner. We adopt a flexible query language in which users specify m quads of the form (subject, property, object, time), using constants or variables. The time component denotes the instant at which a particular edge is valid, and users may also include order relations between temporal constants or variables. The answer to such extended BGPs is the set of all valid variable assignments, including those that involve time. We describe an index structure that, for a temporal graph with N edges, requires O(N) space and can evaluate extended BGPs in worst-case optimal time O(Q* m log N), where Q* represents the maximum number of solutions for query Q over any temporal graph with the same number of instants of edge validities. We use our index to adapt Leapfrog Triejoin to the temporal graph setting and can therefore consider any variable evaluation ordering. Moreover, the same index yields worst-case-optimal guarantees for related query types, including snapshot evaluation, version queries, and other temporal variants. Experiments on real-world datasets show that our approach answers realistic queries in milliseconds with minimal space overhead.