Graph challenge

From: Chris Jones (chjones_at_dacafe.com)
Date: 04/13/04 

Date: 13 Apr 2004 02:31:10 -0700

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.

Relevant Pages

  • Graph challenge
    ... We have a graph and nodes in the graph are to be placed onto a layout. ... edges crossing the partition is minimized. ...
    (comp.programming)
  • Re: vertices in graph vertex covers
    ... A graph where every vertex is of degree 2 ... a partition shares an edge with another ... Dependent: A variable where the assignment depends on ... For every satisfying assignment where v ...
    (sci.math.research)
  • Constructing Quotient Graphs
    ... If we partition N into k parts. ... We define the "Quotient graph" with respect to the above partition as: ... running time O+size). ...
    (comp.programming)
  • Graph Partitioning Problem
    ... I have an application where I want to find a minimum weight partition ... of an undirected graph into k connected components such that each ... All the graph partitioning algorithms and programs I've seen ... Does anybody know of any algorithms, ...
    (comp.theory)
  • Graph Theory: Cuts, Minimal Cuts and Bonds
    ... These definitions are from Reinhard Diestel's "Graph Theory, ... minimal or maximal sets of vertices or edges, ... We denote the set of this edges in E (edge set of ... partition is called a cut. ...
    (sci.math)