Efficient Algorithms for Drawing Large Genealogy Trees

Abstract

Efficient Algorithms for Drawing Large Genealogy Trees tackles the visualization of extensive family networks marked by multiple roots, undirected cycle, and missing family information. Conventional tree drawings assume a single root, strict acyclicity, and uniform branching—constraints routinely violated in genealogies. This work first adapts and evaluates foundational graph‐drawing techniques— force‐directed layouts and the Sugiyama layered framework—to assess their fit for genealogical data. Two distinct strategies then address scale and clarity: a clustering approach that aggregates closely related individuals into higher‐level units to reduce displayed complexity, and a novel fractal drawing method that represents each person as a rectangle recursively subdividing its area among descendants. In the fractal method, subdivisions alternate between horizontal and vertical at each generation, and a space‐allocation function ensures larger or important subfamilies receive more room. A complete C++ implementation applies these approaches to synthetic benchmarks and a Habsburg dataset of over 30,000 individuals. The combination of domain-aware adaptations, information-reducing clustering, and recursive subdivision results in efficient, visually coherent algorithms for static visualization of large genealogy trees.