GSOC 2026: New function pgr_makeBiconnectedPlanar to be added in pgRouting

[Mohit242-bit]

pgr_makeBiconnectedPlanar():

makeBiconnectedPlanar(): Biconnected planar augmentation is an algorithm that takes a connected planar graph and adds edges to eliminate articulation points (vertices whose removal would disconnect the graph), making the graph strictly biconnected while ensuring it remains perfectly planar (no crossed edges). Biconnectivity is a fundamental structural requirement for many advanced planar graph layout and canonical ordering algorithms. This implementation uses the Boost Graph Library's make_biconnected_planar algorithm with a time complexity of O(V + E), where V is the number of vertices and E is the number of edges. This will enhance pgRouting's capabilities in planar graph optimization and spatial rendering problems.

The algorithm:

• Works on undirected graphs.
• Requires the input graph to already be connected and planar.
• Adds new edges between vertices strictly preserving the planarity of the embedding.
• Outputs the set of edges added to the graph to make it biconnected.
• Running time: O(V + E) where V is the number of vertices and E is the number of edges.

Signature:

• pgr_makeBiconnectedPlanar()

pgr_makeBiconnectedPlanar(Edges SQL)

Returns set of (seq, start_vid, end_vid)
OR EMPTY SET

Parameters

Parameter	Type	Description
Edges SQL	TEXT	Inner SQL query, as described below.

Inner Query

Edges SQL: An SQL query returning a set of rows with the following columns:

Column	Type	Default	Description
id	ANY-INTEGER		Identifier of the edge.
source	ANY-INTEGER		Identifier of the first endpoint vertex of the edge.
target	ANY-INTEGER		Identifier of the second endpoint vertex of the edge.
cost	ANY-NUMERICAL		Weight of the edge (source, target). When negative, the edge does not exist.
reverse_cost	ANY-NUMERICAL	-1	Weight of the edge (target, source). When negative, the edge does not exist.

Where:

• ANY-INTEGER = SMALLINT, INTEGER, BIGINT
• ANY-NUMERICAL = SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result Columns

Returns SETOF (seq, start_vid, end_vid).

Column	Type	Description
seq	BIGINT	Sequential value starting from 1.
start_vid	BIGINT	Identifier of the first endpoint vertex of the added edge.
end_vid	BIGINT	Identifier of the second endpoint vertex of the added edge.