pgr_isPlanar
- Experimental¶
pgr_isPlanar
— Returns a boolean depending upon the planarity of the graph.
Warning
Possible server crash
These functions might create a server crash
Warning
Experimental functions
They are not officially of the current release.
They likely will not be officially be part of the next release:
The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
Name might change.
Signature might change.
Functionality might change.
pgTap tests might be missing.
Might need c/c++ coding.
May lack documentation.
Documentation if any might need to be rewritten.
Documentation examples might need to be automatically generated.
Might need a lot of feedback from the comunity.
Might depend on a proposed function of pgRouting
Might depend on a deprecated function of pgRouting
Availability
Version 3.2.0
New experimental function
Description¶
A graph is planar if it can be drawn in two-dimensional space with no two of its edges crossing. Such a drawing of a planar graph is called a plane drawing. Every planar graph also admits a straight-line drawing, which is a plane drawing where each edge is represented by a line segment. When a graph has \(K_5\) or \(K_{3, 3}\) as subgraph then the graph is not planar.
The main characteristics are:
This implementation use the Boyer-Myrvold Planarity Testing.
It will return a boolean value depending upon the planarity of the graph.
Applicable only for undirected graphs.
The algorithm does not considers traversal costs in the calculations.
Running time: \(O(|V|)\)
Signatures¶
Summary
BOOLEAN
SELECT * FROM pgr_isPlanar(
'SELECT id, source, target, cost, reverse_cost
FROM edges'
);
pgr_isplanar
--------------
t
(1 row)
Parameters¶
Parameter |
Type |
Description |
---|---|---|
|
Edges SQL as described below. |
Inner Queries¶
Edges SQL¶
Column |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Where:
- ANY-INTEGER:
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Result Columns¶
Returns a boolean (pgr_isplanar)
Column |
Type |
Description |
---|---|---|
|
|
|
Additional Examples¶
The following edges will make the subgraph with vertices {10, 15, 11, 16, 13} a \(K_1\) graph.
INSERT INTO edges (source, target, cost, reverse_cost) VALUES
(10, 16, 1, 1), (10, 13, 1, 1),
(15, 11, 1, 1), (15, 13, 1, 1),
(11, 13, 1, 1), (16, 13, 1, 1);
INSERT 0 6
The new graph is not planar because it has a \(K_5\) subgraph. Edges in blue represent \(K_5\) subgraph.
SELECT * FROM pgr_isPlanar(
'SELECT id, source, target, cost, reverse_cost
FROM edges');
pgr_isplanar
--------------
f
(1 row)
See Also¶
Indices and tables