No labeling has been computed yet.
Geophylogenies are a common type of diagram for visualizing the evolutionary history of species in a geographic context.
A geophylogeny consists of a phylogenetic tree T and a set of point features (''sites'') in a rectangular map range, where each leaf of T is associated with a site.
One way to visualize a geophylogeny is to draw the tree downward planar, its leaves placed at equidistant positions on the upper boundary of the map, and connect each leaf to its corresponding site by a straight-line leader.
For this visualization style, prior work by Klawitter, Klesen, Scholl, van Dijk, and Zaft studied the problem of obtaining an embedding of the tree T that minimizes the number of crossings between the leaders.
With this project, we explore paged geophylogenies, where the leaders can partitioned into multiple pages where only crossings within a page are counted. To this end, we are interested in a coloring of the leaders with the fewest number of colors such that leaders of the same color do not cross. We can view each color as a page in a paged drawing of the geophylogeny. We study general and tree-consistent colorings, where in the latter each page must contain only leaders for a single subtree.
The sidebar on the left contains all relevant options to interact with the application. First, you can load an instance of the problem by either uploading a file or selecting one of the sample instances. We provide three real-world instances, which can be loaded using the dropdown menu in the sidebar. You can also upload a labeling file to visualize a pre-computed labeling.
Once an instance has been loaded into the application, you can compute a labeling for it by selecting an objective function and clicking the "Compute Labeling" button. In particular, you can
Once an instance has been loaded or a labeling has been computed, you can get further information about the instance (and the labeling) by accessing its "Properties" via the header bar.
You can also download the current labeling as an SVG, PNG, or JSON file via the "Download Labeling" dropdown in the header bar.
If the labeling was computed using the tree-consistent option, you can click on a colored node in the tree to obtain a leader-length minimized labeling of the selected sub-tree that maintains the same left-to-right order of the leaves as in the original tree.
You can return to the full tree by clicking the "Back to Full Tree" button in the header bar.
Feel free to check out our paper at GD 2026, the full version on arXiv, or the source code on OSF.
How to cite:
@inproceedings{DvDN.PG.2026,
author = {Depian, Thomas and van Dijk, Thomas C. and Nöllenburg, Martin},
title = {Paged Geophylogenies: {A} Coloring Approach to External Labeling with Tree Constraints},
booktitle = {34th International Symposium on Graph Drawing and Network Visualization (GD 2026)},
year = {2026},
editor = {Löffler, Maarten and Miksch, Silvia},
volume = {396},
pages = {8:1--8:21},
series = {LIPIcs},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
doi = {10.4230/LIPIcs.GD.2026.8},
}For further questions about this application, feel free to contact Thomas Depian.
This work received funding from the Vienna Science and Technology Fund (WWTF) project nr. 10.47379/ICT22029.
The real-world instances were taken from Klawitter, Klesen, Scholl, van Dijk, and Zaft; see also this repository.
This prototype was built using