GSoC 2026: Final Report | Implementing Make Biconnected Algorithm and Make Maximal Planar Algorithm to pgRouting

Initiatives Google Summer of Code
,
1

Hello everyone,

With GSoC coming to an end, I hereby present my final report of the work I have done over the past three months. It has been an amazing learning experience and a great time working with the pgRouting community and mentors.

Title: Implementing make_biconnected_planar and make_maximal_planar Algorithms for pgRouting from the Boost Graph Library

Organisation: pgRouting under the umbrella of OSGeo

Abstract: This GSoC project dealt with the implementation of two new planar graph algorithms in pgRouting. The algorithms are described below:

  • pgr_makeBiconnectedPlanar: This algorithm takes a planar graph and adds edges to eliminate articulation points (vertices whose removal would disconnect the graph), making it biconnected while strictly preserving its planarity. Biconnectivity is a fundamental requirement for many advanced graph layout algorithms.
  • pgr_makeMaximalPlanar: This algorithm triangulates a biconnected planar graph by adding edges until no more edges can be added without violating planarity (resulting in a graph where every face is a triangle, satisfying Euler’s formula E = 3V - 6).

Together with the existing pgr_makeConnected, these functions complete pgRouting’s planar graph pipeline (makeConnected → makeBiconnectedPlanar → makeMaximalPlanar), unlocking downstream Boost layout algorithms like Chrobak-Payne straight line drawing.

State of the Project Before GSoC: pgRouting already provided pgr_makeConnected and planarity testing via pgr_isPlanar. However, there were two concrete gaps: no function to eliminate articulation points while preserving planarity, and no triangulation of biconnected planar graphs. This left advanced planar graph drawing and canonical ordering functions completely inaccessible to pgRouting users.

State of the Project After GSoC: The deliverables are complete. Both pgr_makeBiconnectedPlanar and pgr_makeMaximalPlanar have been fully implemented in C++ using the modern coloring_driver architecture. The deliverables include the core code, comprehensive RST user documentation, documentation queries, and a robust suite of pgTAP edge-case tests (handling 0-vertex, single-vertex, disconnected components, and non-planar rejection).

Potential Future Work:

  • After the completion of the program, I will focus on resolving any potential bugs or usability issues that may come up during extended community testing.
  • The completion of this pipeline now opens the door for implementing the actual drawing algorithms (chrobak_payne_straight_line_drawing and planar_canonical_ordering). I would like to explore implementing these downstream functions so users can generate 2D coordinates for planar graphs directly inside PostGIS.

Links:

I am so grateful to be a part of the amazing GSoC and OSGeo communities. I have learned a massive amount during this program, which has helped me improve my C++ architecture skills, my understanding of the Boost Graph Library, and how to effectively contribute to open source. Last but not least, a huge thank you to my mentors and the entire community for the continuous support, guidance, and helpful communication!

Thank you and Regards,

Mohit Rawat