Deprecated: Methods with the same name as their class will not be constructors in a future version of PHP; plgContentJComments has a deprecated constructor in /var/www/astarmathsandphysics/plugins/content/jcomments/jcomments.php on line 25 Call Stack: 0.0000 362664 1. {main}() /var/www/astarmathsandphysics/index.php:0 0.0462 1212104 2. Joomla\CMS\Application\SiteApplication->execute() /var/www/astarmathsandphysics/index.php:49 0.0462 1212104 3. Joomla\CMS\Application\SiteApplication->doExecute() /var/www/astarmathsandphysics/libraries/src/Application/CMSApplication.php:267 0.1569 4193224 4. Joomla\CMS\Application\SiteApplication->dispatch() /var/www/astarmathsandphysics/libraries/src/Application/SiteApplication.php:233 0.1582 4220904 5. Joomla\CMS\Component\ComponentHelper::renderComponent() /var/www/astarmathsandphysics/libraries/src/Application/SiteApplication.php:194 0.1589 4238616 6. Joomla\CMS\Component\ComponentHelper::executeComponent() /var/www/astarmathsandphysics/libraries/src/Component/ComponentHelper.php:356 0.1591 4269136 7. require_once('/var/www/astarmathsandphysics/components/com_content/content.php') /var/www/astarmathsandphysics/libraries/src/Component/ComponentHelper.php:381 0.1601 4291856 8. ContentController->execute() /var/www/astarmathsandphysics/components/com_content/content.php:42 0.1601 4291856 9. ContentController->display() /var/www/astarmathsandphysics/libraries/src/MVC/Controller/BaseController.php:710 0.2132 4963944 10. ContentController->display() /var/www/astarmathsandphysics/components/com_content/controller.php:113 0.2168 5156096 11. Joomla\CMS\Cache\Controller\ViewController->get() /var/www/astarmathsandphysics/libraries/src/MVC/Controller/BaseController.php:663 0.2174 5177024 12. ContentViewArticle->display() /var/www/astarmathsandphysics/libraries/src/Cache/Controller/ViewController.php:102 0.2280 5372536 13. Joomla\CMS\Plugin\PluginHelper::importPlugin() /var/www/astarmathsandphysics/components/com_content/views/article/view.html.php:189 0.2280 5372792 14. Joomla\CMS\Plugin\PluginHelper::import() /var/www/astarmathsandphysics/libraries/src/Plugin/PluginHelper.php:182

An Algorithm for Determining Whether or Not a Graph is Planar

A graph is planar if it can be drawn in such a way that no arc crosses any other arc. There are algorithms for determining whether or not a graph is planar. The algorithm below can only be applied to graphs that have a Hamiltonian cycle (a cycle that passes through every vertex of the graph once and only once, and returns to its start vertex)

1. Identify a Hamiltonian cycle in the graph

2. Redraw the graph so that the Hamiltonian cycle forms a regular polygon and all edges are drawn as straight lines in the polygon

3. Choose any edge AB and decide this will stay inside the polygon

4. Consider any edges that cross AB

(a) if it is possible to move all these outside without producing crossings, go to step 5

(b) if it is not possible then the graph is non planar

5. Consider each remaining crossing inside and see if any edge may be moved outside to remove it, without creating a crossing inside

6. Stop when all crossings inside have been considered

(a) if there are no crossings inside or outside then the graph is planar

(b) if there is a crossing inside that cannot be removed then the graph is non-planar

Example: Applying the algorithm to the graph below

Results in the Hamiltonian path ABCD below

The edge BD can stay inside the polygon. AC can move outside the polygon and no arcs cross so the graph is planar.

The graph below is not planar. The arcs BE and BD can be moved outside the polygon but then the arc CE still crosses the arc AC and cannot be moved outside without crossing one of the newly outside arcs BE or BD.