GSOC 2026: New function pgr_makeMaximalPlanar to be added in pgrouting

[Mohit242-bit]

pgr_makeMaximalPlanar():

makeMaximalPlanar(): Maximal planar augmentation (triangulation) is an algorithm that takes a biconnected planar graph and adds edges until the graph becomes maximally planar. A graph is maximally planar if no more edges can be added without violating planarity, which results in a triangulated graph where every face is a triangle (satisfying Euler's formula E = 3V - 6). Triangulated planar graphs are required for advanced graph layout algorithms like Chrobak-Payne straight line drawing. This implementation uses the Boost Graph Library's make_maximal_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 biconnected and planar.
• Adds new edges between vertices strictly preserving the planarity of the embedding.
• Outputs the set of edges added to the graph to triangulate it.
• Running time: O(V + E) where V is the number of vertices and E is the number of edges.

Signature:

• pgr_makeMaximalPlanar()

pgr_makeMaximalPlanar(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.