GSoC 2026 : Community Bonding Report - Implement Make Biconnected Planar and Make Maximal Planar Algorithms for pgRouting

Initiatives Google Summer of Code
1

Name: Mohit Rawat
Project Title: Implement Make Biconnected Planar and Make Maximal Planar Algorithms for pgRouting.

Mentors: @cvvergara, @robe, @krashish8
Organization: OSGeo / pgRouting
OSGeo Profile: OSGeo Profile Link
Project Wiki: Github Wiki Link
Repository: Repo Link

Period: Community Bonding (May 1 – May 25, 2026)

Work Done in Community Bonding Period

OSGeo and Project Onboarding

  • Introduced myself on pgrouting-dev and soc@osgeo mailing lists.
  • Attended bonding period meeting with mentors.
  • Set up GSoC wiki progress page with weekly reporting structure, goals, and deliverables.

Deep Codebase Study

  • Studied boyer_myrvold_planarity_test embedding generation , understood how the PlanarEmbedding parameter stores the cyclic edge ordering per vertex as a side-effect.
  • Studied planar_face_traversal visitor workflow traced all 7 phases of triangulation_visitor::end_face() including the timestamp trick for O(1) neighbor marking.
  • Studied the full pgRouting execution pipeline: SQL → C wrapper (SRF) → C++ driver → Boost algorithm → result mapping back to pgRouting IDs.
  • Read existing codebase files that my implementation will follow: makeConnected.hpp, makeConnected_driver.cpp,base_graph.hpp, basic_edge.hpp.

Standalone C++ Tests

  • Ran standalone test of boost::make_biconnected_planar — verified on a different types of graphs that biconnectivity is preserved and planarity is maintained after augmentation. (test_biconnected.cpp)
  • Ran standalone test of boost::make_maximal_planar verified on different types of graphs that the full pipeline (connected → biconnected → maximal planar) produces exactly 3V−6 = 9 edges and 2V−4 = 6 faces, confirming Euler’s formula. (test_maximalplanar.cpp)

Pseudocode for Both C++ Wrappers

Proposal revision : After studying triangulation_visitor::end_face() in detail, I confirmed that the visitor for makeMaximalPlanar must be mutating (calling add_edge() inside visit_vertex_pair).

Community Interaction

  • Actively Participated in discussions with mentor.
  • Discussed Edge cost assignment strategy for newly added edges with mentors .

Plans for the Coding Period

  • Start implementing Make biconnected and Make maximal planar algorithms by integrating with the Boost Graph Library.
  • Continuously update the wiki page and weekly report as progress is made.

Am I blocked on anything?

No, I am not currently blocked on anything.

Regards,
Mohit Rawat
OSGeo id: Mohit31
Github:Mohit242-bit