1..
2   ****************************************************************************
3    pgRouting Manual
4    Copyright(c) pgRouting Contributors
5
6    This documentation is licensed under a Creative Commons Attribution-Share
7    Alike 3.0 License: http://creativecommons.org/licenses/by-sa/3.0/
8   ****************************************************************************
9
10|
11
12* **Supported versions:**
13  `Latest <https://docs.pgrouting.org/latest/en/pgr_isPlanar.html>`__
14  (`3.2 <https://docs.pgrouting.org/3.2/en/pgr_isPlanar.html>`__)
15
16pgr_isPlanar - Experimental
17===============================================================================
18
19``pgr_isPlanar`` — Returns a boolean depending upon the planarity of the graph.
20
21.. figure:: images/boost-inside.jpeg
22   :target: https://www.boost.org/libs/graph/doc/boyer_myrvold.html
23
24   Boost Graph Inside
25
26.. include:: experimental.rst
27   :start-after: begin-warn-expr
28   :end-before: end-warn-expr
29
30.. rubric:: Availability
31
32* Version 3.2.0
33
34  * New **experimental** function
35
36
37Description
38-------------------------------------------------------------------------------
39
40A graph is planar if it can be drawn in two-dimensional space with no two of its edges crossing. Such a drawing
41of a planar graph is called a plane drawing. Every planar graph also admits a straight-line drawing, which is a
42plane drawing where each edge is represented by a line segment. When a graph has :math:`K_5` or :math:`K_{3,3}` as subgraph then the
43graph is not planar.
44
45The main characteristics are:
46  - This implementation use the Boyer-Myrvold Planarity Testing.
47
48  - It will return a boolean value depending upon the planarity of the graph.
49
50  - Applicable only for **undirected** graphs.
51
52  - The algorithm does not considers traversal costs in the calculations.
53
54  - Running time: :math:`O(|V|)`
55
56Signatures
57-------------------------------------------------------------------------------
58
59.. rubric:: Summary
60
61.. code-block:: none
62
63    pgr_isPlanar(Edges SQL) -- Experimental on v3.2
64
65    RETURNS BOOLEAN
66
67.. literalinclude:: doc-pgr_isPlanar.queries
68   :start-after: -- q1
69   :end-before: -- q2
70
71.. index::
72   single: isPlanar(Edges SQL) -- Experimental on v3.2
73
74Parameters
75-------------------------------------------------------------------------------
76
77=================== ====================== ========= =================================================
78Parameter           Type                   Default   Description
79=================== ====================== ========= =================================================
80**Edges SQL**       ``TEXT``                         SQL query as described below.
81=================== ====================== ========= =================================================
82
83Inner query
84-------------------------------------------------------------------------------
85
86:Edges SQL: an SQL query, which should return a set of rows with the following columns:
87
88================= =================== ======== =================================================
89Column            Type                 Default  Description
90================= =================== ======== =================================================
91**id**            ``ANY-INTEGER``                Identifier of the edge.
92**source**        ``ANY-INTEGER``                Identifier of the first end point vertex of the edge.
93**target**        ``ANY-INTEGER``                Identifier of the second end point vertex of the edge.
94**cost**          ``ANY-NUMERICAL``              - When positive: edge `(target, source)` is part of the graph.
95                                                 - When negative: edge `(target, source)` is not part of the graph.
96
97**reverse_cost**  ``ANY-NUMERICAL``       -1     - When positive: edge `(target, source)` is part of the graph.
98                                                 - When negative: edge `(target, source)` is not part of the graph.
99
100================= =================== ======== =================================================
101
102Where:
103
104:ANY-INTEGER: SMALLINT, INTEGER, BIGINT
105:ANY-NUMERICAL: SMALLINT, INTEGER, BIGINT, REAL, FLOAT
106
107Result Columns
108-------------------------------------------------------------------------------
109
110Returns a boolean ``(pgr_isplanar)``
111
112=================  =========== ============================================================
113Column             Type        Description
114=================  =========== ============================================================
115**pgr_isplanar**   ``BOOLEAN`` - `true` when the graph is planar.
116                               - `false` when the graph is not planar.
117=================  =========== ============================================================
118
119Additional Example:
120-------------------------------------------------------------------------------
121
122The following edges will make the subgraph with vertices {3, 4, 6, 9, 16} a :math:`K_5` graph.
123
124.. literalinclude:: doc-pgr_isPlanar.queries
125   :start-after: -- q2
126   :end-before: -- q3
127
128The new graph is not planar because it has a :math:`K_5` subgraph. Edges in blue represent :math:`K_5` subgraph.
129
130.. image:: images/nonPlanar.png
131   :scale: 50%
132
133.. literalinclude:: doc-pgr_isPlanar.queries
134   :start-after: -- q3
135   :end-before: -- q4
136
137See Also
138-------------------------------------------------------------------------------
139
140* https://www.boost.org/libs/graph/doc/boyer_myrvold.html
141* The queries use the :doc:`sampledata` network.
142
143.. rubric:: Indices and tables
144
145* :ref:`genindex`
146* :ref:`search`
147