1 of 17

2020

2 of 17

Himanshu Raj

3 of 17

pgRouting Boyer Myrvold Planarity Testing

What are planar Graphs:-

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.
When a graph has K₅ or K_3,3 as subgraph then the graph is not planar.

4 of 17

pgRouting Boyer Myrvold Planarity Testing

Some Non-Planar Graphs :-

K₅

K_3,3

5 of 17

pgRouting Boyer Myrvold Planarity Testing

Planarity Testing algorithm:

Return a boolean value depending upon the planarity of the graph.
Applicable only on undirected graphs.
Does not considers traversal costs in the calculations.

Time complexity : O(|V|)

6 of 17

pgRouting Boyer Myrvold Planarity Testing

CREATE TABLE edge_table (

id BIGSERIAL,

source BIGINT,

target BIGINT,

cost FLOAT,

reverse_cost FLOAT);

INSERT INTO edge_table

(source, target, cost, reverse_cost) VALUES

(1, 2, 1, 1), (2, 3, 1, 1),

(3, 4, 1, 1), (4, 5, 1, 1),

(5, 1, 1, 1);

3

1

5

4

2

7 of 17

pgRouting Boyer Myrvold Planarity Testing

SELECT * FROM pgr_isPlanar(

'SELECT id, source, target, cost, reverse_cost

FROM edge_table'

);

pgr_isplanar

--------------

t

(1 row)

3

1

5

4

2

8 of 17

pgRouting Boyer Myrvold Planarity Testing

INSERT INTO edge_table

(source, target, cost, reverse_cost) VALUES

(3, 1, 1, 1), (3, 5, 1, 1),

(4, 1, 1, 1), (4, 2, 1, 1),

(5, 2, 1, 1);

SELECT * FROM pgr_isPlanar(

'SELECT id, source, target, cost, reverse_cost

FROM edge_table'

);

pgr_isplanar

--------------

f

(1 row)

3

1

5

4

2

9 of 17

pgRouting Make Connected

Main characteristics of the algorithm:

It will give the minimum list of all edges which are needed in the graph to make the graph connected.
Applicable only for undirected graphs.

Time complexity : O(|V|+|E|)

10 of 17

pgRouting Make Connected

CREATE TABLE edge_table (

id BIGSERIAL,

source BIGINT,

target BIGINT,

cost FLOAT,

reverse_cost FLOAT);

INSERT INTO edge_table

(source, target, cost, reverse_cost) VALUES

(1, 2, 1, 1),(3, 4, 1, 1), (5, 6, 1, 1);

4

2

6

1

5

3

11 of 17

pgRouting Make Connected

SELECT * FROM pgr_makeConnected(

'SELECT id, source, target, cost, reverse_cost

FROM edge_table'

);

seq | start_vid | end_vid

-----+-----------+---------

1 | 2 | 3

2 | 4 | 5

(2 rows)

4

2

6

1

5

3

12 of 17

See Himanshu’s work

13 of 17

The future ....

14 of 17

15 of 17

https://github.com/pgRouting

16 of 17

Thanks!

Presentation under Creative Commons Licence.

17 of 17

Web: pgrouting.org

Documentation: docs.pgrouting.org

workshop: workshop.pgrouting.org

Support: pgrouting.org/support.html

More Information

… or talk to me at

Himanshu Raj raj.himanshu2@gmail.com