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.0001 360848 1. {main}() /var/www/astarmathsandphysics/index.php:0 0.0522 1209592 2. Joomla\CMS\Application\SiteApplication->execute() /var/www/astarmathsandphysics/index.php:49 0.0522 1209592 3. Joomla\CMS\Application\SiteApplication->doExecute() /var/www/astarmathsandphysics/libraries/src/Application/CMSApplication.php:267 0.1689 4037096 4. Joomla\CMS\Application\SiteApplication->dispatch() /var/www/astarmathsandphysics/libraries/src/Application/SiteApplication.php:233 0.1704 4064776 5. Joomla\CMS\Component\ComponentHelper::renderComponent() /var/www/astarmathsandphysics/libraries/src/Application/SiteApplication.php:194 0.1712 4082488 6. Joomla\CMS\Component\ComponentHelper::executeComponent() /var/www/astarmathsandphysics/libraries/src/Component/ComponentHelper.php:356 0.1712 4099496 7. require_once('/var/www/astarmathsandphysics/components/com_content/content.php') /var/www/astarmathsandphysics/libraries/src/Component/ComponentHelper.php:381 0.1719 4107232 8. ContentController->execute() /var/www/astarmathsandphysics/components/com_content/content.php:42 0.1719 4107232 9. ContentController->display() /var/www/astarmathsandphysics/libraries/src/MVC/Controller/BaseController.php:710 0.2106 4337360 10. ContentController->display() /var/www/astarmathsandphysics/components/com_content/controller.php:113 0.2121 4354760 11. Joomla\CMS\Cache\Controller\ViewController->get() /var/www/astarmathsandphysics/libraries/src/MVC/Controller/BaseController.php:663 0.2126 4375688 12. ContentViewArticle->display() /var/www/astarmathsandphysics/libraries/src/Cache/Controller/ViewController.php:102 0.2214 4442400 13. Joomla\CMS\Plugin\PluginHelper::importPlugin() /var/www/astarmathsandphysics/components/com_content/views/article/view.html.php:189 0.2214 4442656 14. Joomla\CMS\Plugin\PluginHelper::import() /var/www/astarmathsandphysics/libraries/src/Plugin/PluginHelper.php:182 Deprecated: Methods with the same name as their class will not be constructors in a future version of PHP; JCommentsACL has a deprecated constructor in /var/www/astarmathsandphysics/components/com_jcomments/classes/acl.php on line 17 Call Stack: 0.0001 360848 1. {main}() /var/www/astarmathsandphysics/index.php:0 0.0522 1209592 2. Joomla\CMS\Application\SiteApplication->execute() /var/www/astarmathsandphysics/index.php:49 0.0522 1209592 3. Joomla\CMS\Application\SiteApplication->doExecute() /var/www/astarmathsandphysics/libraries/src/Application/CMSApplication.php:267 0.1689 4037096 4. Joomla\CMS\Application\SiteApplication->dispatch() /var/www/astarmathsandphysics/libraries/src/Application/SiteApplication.php:233 0.1704 4064776 5. Joomla\CMS\Component\ComponentHelper::renderComponent() /var/www/astarmathsandphysics/libraries/src/Application/SiteApplication.php:194 0.1712 4082488 6. Joomla\CMS\Component\ComponentHelper::executeComponent() /var/www/astarmathsandphysics/libraries/src/Component/ComponentHelper.php:356 0.1712 4099496 7. require_once('/var/www/astarmathsandphysics/components/com_content/content.php') /var/www/astarmathsandphysics/libraries/src/Component/ComponentHelper.php:381 0.1719 4107232 8. ContentController->execute() /var/www/astarmathsandphysics/components/com_content/content.php:42 0.1719 4107232 9. ContentController->display() /var/www/astarmathsandphysics/libraries/src/MVC/Controller/BaseController.php:710 0.2106 4337360 10. ContentController->display() /var/www/astarmathsandphysics/components/com_content/controller.php:113 0.2121 4354760 11. Joomla\CMS\Cache\Controller\ViewController->get() /var/www/astarmathsandphysics/libraries/src/MVC/Controller/BaseController.php:663 0.2126 4375688 12. ContentViewArticle->display() /var/www/astarmathsandphysics/libraries/src/Cache/Controller/ViewController.php:102 0.5961 12235784 13. JEventDispatcher->trigger() /var/www/astarmathsandphysics/components/com_content/views/article/view.html.php:199 0.5963 12236232 14. plgContentJComments->update() /var/www/astarmathsandphysics/libraries/joomla/event/dispatcher.php:160 0.5963 12236232 15. plgContentJComments->onContentAfterDisplay() /var/www/astarmathsandphysics/libraries/joomla/event/event.php:70 0.5965 12244480 16. plgContentJComments->onAfterDisplayContent() /var/www/astarmathsandphysics/plugins/content/jcomments/jcomments.php:339 0.5968 12246216 17. JComments::show() /var/www/astarmathsandphysics/plugins/content/jcomments/jcomments.php:282 0.5974 12279264 18. JCommentsFactory::getACL() /var/www/astarmathsandphysics/components/com_jcomments/jcomments.php:188 0.5975 12279664 19. spl_autoload_call() /var/www/astarmathsandphysics/components/com_jcomments/classes/factory.php:274 0.5975 12279744 20. JLoader::load() /var/www/astarmathsandphysics/components/com_jcomments/classes/factory.php:274

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.

Add comment

Security code
Refresh