Find an Interesting Topic in Graph Theory for an Exam

[BRN]

Homework Statement

Topic concerning graph theory

Relevant Equations

None.

Hello everybody,

I hope it is the right section to post.

For an exam, I should delve into a topic concerning graph theory. My work should include theoretical explanation, pseudo code, correctness analysis, complexity analysis and code implementation (C ++, python or other).

Could someone recommend me an interesting topic to discuss?

Thanks so much!

 

[jedishrfu]

First here are some practice problems that might give you an idea for a more original one:

https://www.geeksforgeeks.org/graph-theory-practice-questions/

and this one:

https://towardsdatascience.com/common-graph-theory-problems-ca990c6865f1

Next a list of open problems in graph theory (the latest unsolved problems) which may be a bit beyond your skill:

http://openproblemgarden.org/category/graph_theory

where you might find a numerical solution but yet not be able to prove some conjecture (unless you can find a counter example). Anyway, they are at least worth looking at.

 

[BRN]

Thank you so much!

The last link is very interesting!

 

[r731]

An interesting theoretical topic would be a program that reduces one NP-complete problem in graph theory to another one. See Karp reduction.

 

[sysprog]

This tells of early work by Euler establishing foundations of graph theory and topology:
https://en.wikipedia.org/wiki/Seven_Bridges_of_Königsberg

This introduces the Chinese Postman Problem, and the Travelling Salesman Problem, or Salesman's Route Problem (an archetype of NP-complete problems): https://en.wikipedia.org/wiki/Route_inspection_problem

This is a linear-time algorithm for finding a minimum-weight spanning tree: https://en.wikipedia.org/wiki/Prim's_algorithm

And planarity testing is important in the design of micro-circuitry:
https://en.wikipedia.org/wiki/Planarity_testing
https://www.eeeguide.com/methods-of-circuit-analysis/

For some background on the history of implementation of planarity in integrated circuits, before the importance of that became generally appreciated, please look at:
https://www.edn.com/noyce-receives-1st-ic-patent-april-25-1961/
https://www.edn.com/noyce-conceives-planar-ic-january-23-1959/

 

[haruspex]

A topical area would be networks in epidemiology.