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