Newsgroups: comp.parallel.mpi
From: clangis@chat.carleton.ca (Christian Langis)
Subject: tuff graph QUESTION
Organization: Carleton U.
Date: Tue, 10 Mar 1998 22:33:50 GMT
Message-ID: <3505bfc5.11336781@news-server.carleton.ca>

Hi there. 
	I am a graduate student in Comp. Sci.	In my current
research, I have to find a solution to a tuff problem. It is a very
specific&theorical question on graphs: 

Let me here expose the problem more specifically. There is an
arbitrary planar graph G whose faces are all triangles (this is
important). These graphs are called triangle meshes (used in computer
graphics). Now, the problem is to separate G into n distinct regions.
In one word, I am looking for a sequential algorithm that can make
n-subdivisions on any G.

But my research goes much further than that. My goal is to derive a
parallel version (COARSE GRAIN) of this algorithm. So, needless to say
that I am also looking for a parallel algorithm that does the same
thing.

In a typical implementation, at the end of execution, each processor
is left with a distinct piece (subgraph Gi, i=[1..n]) of G so that
there is no area of G not covered by one the processors. As of now, my
requirements are not clear, so overlap between subgraph is not a
concern yet.

Anyhow, if you have worked on this problem, know someone who does,
read about it or heard about it... I would be very grateful if you
could send me some references.

		thankx for all