Add Left-Right Planarity test.

[georgios-ts]

This commit implements a new function is_planar that checks if an undirected graph can be drawn in a plane without any edge intersections. The planarity check algorithm is based on the Left-Right Planarity Test.

Reference: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.217.9208

[georgios-ts]

Marking this on hold since it depends on #456.

[coveralls]

Pull Request Test Coverage Report for Build 2064399819

• 425 of 433 (98.15%) changed or added relevant lines in 3 files are covered.
• No unchanged relevant lines lost coverage.
• Overall coverage decreased (-0.01%) to 98.401%

---

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
retworkx-core/src/planar/lr_planar.rs	420	428	98.13%
<!--	Total:	425	433

Totals
Change from base Build 2041483593:	-0.01%
Covered Lines:	11384
Relevant Lines:	11569

---

💛 - Coveralls

[IvanIsCoding]

After #497, you can use the new generator to make some test cases. Table 2 of https://www.sciencedirect.com/science/article/pii/S0166218X08000371 has the crossing numbers of the Petersen graphs, zeros in the table are planar and the rest aren't

[mtreinish]

@georgios-ts is there any update on this? It would be good to get this rebased as @enavarro51 is starting to look at adding a planar_layout() method and having some functionality around lr planarity in retworkx-core would be a good starting off point for that

[georgios-ts]

@mtreinish This should be ready for review now.

[georgios-ts]

@enavarro51 Thanks for taking the time to look into this.

• It's in retworkx-core so we can expose it in our public rust API but there is also a python interface in retworkx that uses internally the implementation written in retworkx-core.
• As you said, to create the embedding we need a PlanarEmbedding structure. This was additional work and I didn't want to overwhelm this PR since it was already quite long. But yeah, I do believe that the creation of the embedding should be separate from the public is_planar test. IMO, we should have two public functions: a test that returns true/false for planar/non-planar graphs and a method that creates a planar layout. All other function/structures (e.g PlanarEmbedding) should be private.
• It sounds like a good plan. After implementing PlanarEmbedding you can leverage the lr_visit_ordered_dfs_tree function to implement Algorithm 6 in the linked paper (the NetworkX equivalent https://github.com/networkx/networkx/blob/main/networkx/algorithms/planarity.py#L650).

If you have any other questions feel free to reach out.

[coveralls]

Pull Request Test Coverage Report for Build 3148280248

• 423 of 431 (98.14%) changed or added relevant lines in 3 files are covered.
• No unchanged relevant lines lost coverage.
• Overall coverage decreased (-0.01%) to 97.095%

---

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
rustworkx-core/src/planar/lr_planar.rs	418	426	98.12%
<!--	Total:	423	431

Totals
Change from base Build 3129997168:	-0.01%
Covered Lines:	13135
Relevant Lines:	13528

---

💛 - Coveralls