# 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

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.

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)