gecko

Abstract

Gecko is a C++ library for solving graph linear arrangement problems. Gecko orders the nodes of a graph, representing data elements, that are connected by edges, representing affinity relations, with the goal of minimizing a chosen functional of edge length. Gecko was primarily designed to minimize the product of edge lengths but can also be used to reduce bandwidth (maximum edge length) and 1-sum (sum of edge lengths), among others. Minimum-edge-product orderings generalize space-filling curve orderings to geometryless graphs and find applications in data locality optimization, graph partitioning, and dimensionality reduction.