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) -- Experimental on v3.2

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