Boost::boyer_myrvold_planarity_test A graph is planar if it can be drawn in two-dimensional space with no two of its edges crossing. Such a drawing of a planar graph is called a plane drawing. Every planar graph also admits a straight-line drawing, which is a plane drawing where each edge is represented by a line segment. When a graph has K5 or K3,3 as subgraph then the graph is not planar. This algorithm is only applicable for undirected graphs. It has a linear time complexity of O(|V|).

Boost::make_connected Adds the minimum number of edges needed to make the input graph connected. The algorithm first identifies all of the connected components in the graph, then adds edges to connect those components together in a path. For example, if a graph contains three connected components A, B, and C, make_connected will add two edges. The two edges added might consist of one connecting a vertex in A with a vertex in B and one connecting a vertex in B with a vertex in C. This algorithm is only applicable for undirected graphs. It has a linear time complexity of O(|V| + |E|).

I propose to add the above two algorithms to pgRouting during the GSoC period.

Organization

Student

Himanshu Raj

Mentors

  • cvvergara
  • Daniel Kastl
close

2020