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

  • 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

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)

See Also

Indices and tables