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 edges'
);
 pgr_isplanar
--------------
 t
(1 row)

Parameters

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

Inner Queries

Edges SQL

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   Weight of the edge (source, target)
reverse_cost ANY-NUMERICAL -1

Weight of the edge (target, source)

  • When negative: edge (target, source) does not exist, therefore it’s 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 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.

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