Algorithms for Geometric Networks

Geometric Networks typically are a sparse subgraphs of  a complete graph defined over a set of points embedded in the plane (or space). There are several algorithms which take a complete graph and compute a sparse subgraph satisfying various constraints, e.g.  low diameter, constant degree and fault-tolerant. In our recent work, we have designed algorithms which compute sparse subgraphs of non-complete graphs. Especially, given a k-partite graph, we construct a sparse subgraph consisting of linear number of edges, and show that the shortest path gets stretched by a constant factor.  This result has appeared in SIAM Jl. Computing 38 (5): 1803—1820, 2009. We want to further broaden the scope of this work with the help of a global link student in the following directions (a) Implementation (b) Experimental Study (c) Possibly come up with an algorithm that constructs a planar  subgrap

Student is first expected to learn the techniques used in the research mentioned above.  Then the student is expected to implement an algorithm, and do an experimental study. If time permits, the student will be mentored to design an algorithm to compute sparse planar subggraphs.

Faculty Supervisor:

Dr. Anil Maheshwari


Amit Gupta



Computer science


Information and communications technologies


Carleton University



Current openings

Find the perfect opportunity to put your academic skills and knowledge into practice!

Find Projects