Logo

Login

Disconnected Graph Layout and the Polyomino Packing Approach

Freivalds, Karlis and Dogrusoz, Ugur and Kikusts, Paulis (2002) Disconnected Graph Layout and the Polyomino Packing Approach. [Conference Paper]

Full text not available from this repository.

Abstract

We review existing algorithms and present a new approach for layout of disconnected graphs. The new approach is based on polyomino representation of components as opposed to rectangles. The parameters of our algorithm and their influence on the drawings produced as well as a variation of the algorithm for multiple pages are discussed. We also analyze our algorithm both theoretically and experimentally and compare it with the existing ones. The new approach produces much more compact and uniform drawings than previous methods.

Item Type:Conference Paper
Classifications:Z Theory > Z.500 Representations
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.999 Others
ID Code:525
Deposited By:Arnopolina, Galina
Deposited On:22 Dec 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2265&spage=378

Repository Staff Only: item control page

References

1. B.S. Baker, E.G. Coffman, and R.S. Rivest. Orthogonal packings in two dimensions. SIAM Journal on Computing, 9(4):846-855, November 1980.

2. E.G. Coffman, M.R. Garey and D.S. Johnson. Approximation algorithms for bin packing: An updated survey. In G. Ausiello, M. Lucertini, and P. Serafini, editors, Algorihtms Design for Computer System Design, pages 49-106. Springer-Verlag, New-York, 1984.

3. E.G. Coffman, M.R. Garey, D.S. Johnson, and R.E. Tarjan. Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing, 9(4):808-826, November 1990.

4. E.G. Coffman and P.W. Shor. Packings in two dimensions: Asymptotic average case analysis of algorithms. Algorithmica, 9:253-277, 1993.

5. G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4: 235-282, 1994.

6. U. Dogrusoz. Algorithms for layout of disconnected graphs. Information Sciences, to appear.

7. U. Dogrusoz, M. Doorley, Q. Feng, A. Frick, B. Madden, and G. Sander. Toolkits for development of software diagramming applications. IEEE Computer Graphics and Applications, to appear.

8. U. Dogrusoz and G. Sander. Graph visualization. ACM Computing Surveys, to appear.

9. M.R. Garey and D.S. Johnson. Computers and Itractability: A Guide to hte theory of NP-Completeness. W.H. Freeman and company, NY, 1979.

10. T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31(1):7-15, April 1989.

11. P. Kikusts and P. Rucevskis. Layout algorithm of graph-like diagrams for grade windows graphic editors. In Symp. on Graph Drawing, GD '95, LNCS 1027, Passau, Germany, September 1995. Springer-Verlag.

12. Thomas Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. John Wiley and Sons, 1990.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.