Company
Date Published
July 4, 2024
Author
CARTO Contributors
Word count
1932
Language
English
Hacker News points
None

Summary

At CARTO, they challenge themselves to use their platform as their users do, understanding better the pains and gains of using it. This approach helps them learn a lot about SQL, React, WebGL, projections, spatial algorithms, and mapping. They applied graph coloring to maps, which is a technique to assign colors to vertices in a graph so that no two adjacent vertices share the same color. Map coloring is an application of graph coloring, assigning different colors to adjacent polygons (countries, provinces, etc.). The Welsh-Powell algorithm is a greedy coloring approach, while Kempe's graph coloring algorithm adds nodes back to the graph in reverse order from which they were removed, coloring each added node with a color not used by its neighbors. These algorithms can be implemented as PostgreSQL functions using CARTO's batch SQL API. The resulting table contains a color assigned for each cartodb_id, and the original world_borders table can be joined with this table to visualize the result. The Kempe's graph coloring algorithm is more complex than the Welsh-Powell algorithm but still solvable using a pure PostgreSQL function.