We have a graph and nodes in the graph are to be placed onto a layout. The layout has to be partitioned vertically as well as horizontally several times till it generates one slot per node. Nodes are to be assigned to vertical and horizontal partitions such that the number of edges crossing the partition is minimized. Can anybody suggest an effective procedure to deal with this problem?
As an example if we have a graph with sixteen nodes then layout has to be partitioned vertically and horizontally till the time it creates sixteen slots one per node. The idea is to decide which slot would go to which node by following the above criteria( i.e number of edges crossing a partition is minimized.
Thanks.