Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

42
votes
7answers
927 views
+100

What is the optimal path between $2$ fixed points around an invisible obstructing wall?

Every day you walk from point A to point B, which are $3$ miles apart. There is a $50$% chance each walk that there is an invisible wall somewhere strictly between the two points (never at A or B). ...
6
votes
0answers
31 views
+50

Heuristics for topological sort

I have a number of modules connected in a Directed Acyclic Graph. My problem is to find an optimal execution order (minimize the total execution time). Any topological sort suffices for a valid ...
0
votes
0answers
42 views
+50

Circumscribed Simple Line Arrangements Have Hamiltonian Circuits?

An arrangement of $s$ lines are drawn in the plane so that no three lines intersect at a common point and no two lines are parallel. Now circumscribe this arrangement by a circle so that all ...