Implementing Planar Face Extraction and K-Core Decomposition Algorithms for pgRouting
This project brings two new algorithms from the Boost Graph Library into pgRouting: planar face traversal and k-core decomposition. pgr_planarFaces extracts enclosed city block regions from planar street networks using Boyer-Myrvold planarity testing and BGL planar_face_traversal. The output integrates with PostGIS ST_MakePolygon to build polygon geometries directly from road topology. pgr_coreNumbers computes k-core decomposition using the Batagelj-Zaversnik algorithm, assigning each vertex a core number representing its connectivity level. Core 1 vertices are dead-end streets, core 2 are corridors, and core 3+ form the dense urban grid. Together they create a pipeline: pgr_coreNumbers prunes dead-ends before pgr_planarFaces extracts clean faces. Both run in O(V+E) linear time. If time allows, pgr_isKuratowskiSubgraph will extract the exact K5 or K3,3 subdivision causing non-planarity, completing the planar diagnostic toolkit. pgr_isPlanar is included as a standalone companion function.
Project details
Technologies
Not listed in the archive