pgr_isPlanar - Experimental

pgr_isPlanar — Returns a boolean depending upon the planarity of the graph.

_images/boost-inside.jpeg

Boost Graph Inside

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

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

pgr_isPlanar(Edges SQL)

RETURNS BOOLEAN
SELECT * FROM pgr_isPlanar(
    'SELECT id, source, target, cost, reverse_cost
     FROM edge_table'
);
 pgr_isplanar
--------------
 t
(1 row)

Parameters

Parameter Type Default Description
Edges SQL TEXT   SQL query as described below.

Inner query

Edges SQL:an SQL query, which should return 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 end point vertex of the edge.
target ANY-INTEGER   Identifier of the second end point vertex of the edge.
cost ANY-NUMERICAL  
  • When positive: edge (target, source) is part of the graph.
  • When negative: edge (target, source) is not part of the graph.
reverse_cost ANY-NUMERICAL -1
  • When positive: edge (target, source) is part of the graph.
  • When negative: edge (target, source) is not part of the graph.

Where:

ANY-INTEGER:SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result Columns

Returns a boolean (pgr_isplanar)

Column Type Description
pgr_isplanar BOOLEAN
  • true when the graph is planar.
  • false when the graph is not planar.

Additional Example:

The following edges will make the subgraph with vertices {3, 4, 6, 9, 16} a \(K_5\) graph.

INSERT INTO edge_table (source, target, cost, reverse_cost) VALUES
(3, 9, 1, 1), (3, 16, 1, 1),
(4, 6, 1, 1), (4, 16, 1, 1),
(6, 16, 1, 1),
(9, 16, 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.

_images/nonPlanar.png
SELECT * FROM pgr_isPlanar(
    'SELECT id, source, target, cost, reverse_cost
     FROM edge_table'
);
 pgr_isplanar
--------------
 f
(1 row)

See Also

Indices and tables