Non-plannar graph placement algorithm wanted

Article View: alt.msdos.programmer

Article #1122

Back to alt.msdos.programmer Previous Next

#1122

From: Alexander A. Apostolovski
Date: Tue, 22 Mar 1994 14:21

58 lines
2729 bytes



INTRODUCTION
--------------------------------------------------------------------
I am currently working as a trainee at the University of Twente.
The goal is to make a placement algorithm for non-plannar graphs.
--------------------------------------------------------------------


QUESTION :
--------------------------------------------------------------------
My question : Does anyone know if there is a placement algorithm for
              non-plannar graphs ? 
              Anything would be great !
--------------------------------------------------------------------


EXPLANATION OF THE PLACEMENT ALGORITHM
--------------------------------------------------------------------
Our program makes graphs consisting of nodes, edges and access points.

The current placement algorithm isn't working very wel. It takes all
nodes out of the database and places them, without other checking.
(Like : minimizing crossing lines)

I now give a example of a graph placement.

     current view           better example of the same graph
     ============          ==================================

     (v1)(v2)(v3)               (v2)    (v3)     (v1)
       \  /   /|                  \      / \      /
        \/   / |                  (++)  /   \    /
        /\  /  |                    \  /     \  /
       /  \/   |                     (+)      (-) 
     (++) /\   |                       \      /        
       \ /  \  |       ===>             \    /
       (+)   \ |                         \  /
         \    (-)                         (+)
          \    |                           |
           \   |                           |
            \  |                          (=)
             \ |
              (+)
               |
              (=)

( )  -> are nodes
--------------------------------------------------------------------


Thank you for reading my question and I would be more gradefull
if you could help me sloving my placement problem.
Thanks in advance.

Alexander Apostolovski
apostolo@cs.utwente.nl

Technical Details

Message-ID: <1994Mar22.152115@cs.utwente.nl>

Path:

arc1-ca.pugleaf.net!wupost!howland.reston.ans.net!pipex!sunic!EU.net!sun4nl!news.nic.surfnet.nl!utciva.civ.utwente.nl!infnews.cs.utwente.nl!apostolo

Show Full Headers

Complete Article Headers

Newsgroups: alt.msdos.programmer,alt.sources,alt.sources.d,alt.sources.wanted,comp.lang.c,comp.lang.c++,comp.sources.d,comp.sources.wanted,comp.std.c,comp.std.c++
Path: arc1-ca.pugleaf.net!wupost!howland.reston.ans.net!pipex!sunic!EU.net!sun4nl!news.nic.surfnet.nl!utciva.civ.utwente.nl!infnews.cs.utwente.nl!apostolo
From: apostolo@cs.utwente.nl (Alexander A. Apostolovski)
Subject: Non-plannar graph placement algorithm wanted
Message-ID: <1994Mar22.152115@cs.utwente.nl>
Sender: usenet@cs.utwente.nl
Nntp-Posting-Host: rijn.cs.utwente.nl
Organization: Twente University, Dept. of Computer Science
Date: Tue, 22 Mar 1994 14:21:15 GMT
Lines: 60