GSOC 2026: New function pgr_planarFaces to be added in pgRouting

[sakirr05]

pgr_planarFaces():

planarFaces(): Planar face extraction is an algorithm that takes an undirected planar graph, computes a planar embedding of it, and walks every face of that embedding. A face is a maximal connected region of the plane bounded by edges, which on a street network corresponds to the city blocks between the roads, and the exterior face is the unbounded region outside the outermost cycle. Once an embedding is fixed each edge separates exactly two faces, bordering one on its left side and the other on its right, so the function reports every edge-face incidence. This implementation uses the Boost Graph Library's boyer_myrvold_planarity_test to compute the embedding and planar_face_traversal to walk the faces, 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 topology extraction and polygon reconstruction problems.

The algorithm:

• Works on undirected graphs.
• Edge direction and traversal costs are ignored, only the edge endpoints matter.
• Requires the input graph to be planar, otherwise raises ERROR: Graph is not planar. Use pgr_isPlanar first when planarity is unknown.
• Reports one row per edge side, so the result has 2|E| rows.
• Walks the outer face of every connected component separately, so on a graph with C components the face count satisfies |V| - |E| + |F| = 2C.
• Running time: O(V + E) where V is the number of vertices and E is the number of edges.

Signature:

• pgr_planarFaces()

pgr_planarFaces(Edges SQL)

Returns set of (seq, face_id, edge_id, side)
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, face_id, edge_id, side).

Column	Type	Description
seq	BIGINT	Sequential value starting from 1.
face_id	BIGINT	Identifier of the face in the computed embedding.
edge_id	BIGINT	Identifier of the edge that borders the face.
side	INTEGER	1 when the edge borders the face on the left side, 2 when on the right side.