Graph Theory - A visualization tool for the cutwidth problem on graphs
- Accept input input in json format(see .json examples).
- Graphs must be tree representation of quasi-threshold(or theshold).
- If minimum cutwidth is known it can be put in json in the "minimumCutwidth" field.
- Supports pre-saved linear orderings in "order" field.
- You can interact with the graph, move around nodes ,add/remove nodes or adjust their sizes by will.
- Cutwidth for the current linear order is shown.
- Use the help button for more information on how to use
All functionality is inline in one file so this can be loaded locally in browser without the use of a server. The simple version is colorfull, but there is the modified-colors version which is black and white for use in screenshots etc.
You can execute 3 known algorithms for the graphs.
-
An modified version of the dynamic algorithm described in the paper A Note on Exact Algorithms for Vertex Ordering Problems on Graphs. This algorithm runs in O(2N) and is optimal for all graphs. The modified version runs on cliques instead of vertices.
-
An algorithm for threshold graphs as described in tha paper Cutwidth of split graphs and threshold graphs. This algorithm runs in linear time O(n). Optimal for threshold graphs.
-
An polynomial time algorithm that is optimal only for 1-level quasi-threshold graphs. Runs in O(nN) time.
-
Click on a node in the tree to add a new child.
-
Alt + Click on a node in the tree to remove it and it's children.
-
Mouseover on a node and press + or - to adjust its size
-
Shift + , or Shift + . to move to the next/previous order saved in input file.
-
Mouseover on a node and press o to find an order for that node and its children using the bitonic algorithm as proposed by us.
-
Press Shift + D to find a linear ordering using the Dynamic Programming algorithm
-
Press Shift + T to find a linear ordering using the using the Threshold Algorithm
-
~ to open up debug information. Then Mouseover a node to see it's specified debug info.