Hi Joe,

With "an index on type and range" you really mean:

mgmt.buildIndex('byTypeAndRange', Vertex.class).addKey(type).addKey(range).buildCompositeIndex()

Indeed, supernodes have little value in traversing graphs. Maybe you can remove the worst ones (they probably have little meaning) or make them into a property on the attached vertices.
If the supernodes are not the ones you want to traverse in your query, maybe a label constraint in the index can help.

Best wishes,    Marc