Представление графа в памяти для быстрого доступа к его элементам

Имея большие и очень большие графы размещённые на плоскости, необходимо быстро определять видимые объекты (часть графа в определённом масштабе, когда пользователь что то рассматривает), среди них объекты попадающие под указатель мыши. Граф состоит из узлов и рёбер. Как эффективно организовать представление графа в памяти под эту задачу? Первое решение разбить пространство на квадраты, те, на квадраты поменьше и тд. Далее определять какие квадраты видны, какие к ним привязаны объекты, и уже дальше работать. Но рёбра могут распологаться на нескольких таких квадратах, возникают прочие другие проблемы. Второе решение использовать тот факт что граф связан (а может и не связан), вспомнить о рекурсии... Есть ли решение лучше? Идеи, структуры данных, алгоритмы, когда узлов от 25000 шт и более. Уже какое то время бесполезно просматриваю статьи, литературу