#24118 closed enhancement (fixed)

Add quick check for planarity

Reported by: jmantysalo Owned by:
Priority: minor Milestone: sage-8.2
Component: graph theory Keywords:
Cc: dcoudert Merged in:
Authors: Jori Mäntysalo Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 3db3fb3 (Commits) Commit: 3db3fb363aed577a51c95e3b11873c45dc584c6e
Dependencies: Stopgaps:

Description

Functions to check if a graph is planar or circular planar should first check if the graph has "too many" edges compared to number of vertices and then return False directly.

Change History (4)

comment:1 Changed 15 months ago by jmantysalo

  • Branch set to u/jmantysalo/add_quick_check_for_planarity

comment:2 Changed 15 months ago by jmantysalo

  • Authors set to Jori Mäntysalo
  • Cc dcoudert added
  • Commit set to 3db3fb363aed577a51c95e3b11873c45dc584c6e
  • Milestone changed from sage-8.1 to sage-8.2
  • Status changed from new to needs_review

This is just for most basic use cases. Anyways I think it is good to catch trivial things like these first.


New commits:

3db3fb3Add quick check based on edge/vertex -ratio.

comment:3 Changed 15 months ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

OK, passes all tests.

comment:4 Changed 14 months ago by vbraun

  • Branch changed from u/jmantysalo/add_quick_check_for_planarity to 3db3fb363aed577a51c95e3b11873c45dc584c6e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.