Layered graph layouts with a given aspect ratio

Details Layered graph layouts with a given aspect ratio Layered graph layouts with a given aspect ratio

2011-04-26

2011-04-26

Harrison, Chante (Department: 2628)

Computer graphics processing and selective visual display system

Computer graphics processing

Graph generating

C715S243000, C715S853000, C345S619000

Reexamination Certificate

active

07932907

ABSTRACT:
A graph layout technique that creates a layered graph layout with a given aspect ratio. The present layered graph layout technique better utilizes the available space and, at the same time, creates an aesthetically pleasing drawing of a directed graph. In one embodiment it determines the layout of the new graph based on a modified Sugiyama technique combined with a modified Coffman-Graham scheduling algorithm. Given a directed graph and a desired aspect ratio, it uses a binary search and the Coffman-Graham scheduling algorithm to find a layout of the graph that has an aspect ratio that matches the given aspect ratio of the available space.

REFERENCES:
patent: 5467472 (1995-11-01), Williams et al.
patent: 5887174 (1999-03-01), Simons et al.
patent: 6035061 (2000-03-01), Katsuyama et al.
patent: 6057842 (2000-05-01), Knowlton et al.
patent: 6128023 (2000-10-01), Kawashima
patent: 6490604 (2002-12-01), Toyosawa et al.
patent: 6826727 (2004-11-01), Mohr et al.
patent: 6847979 (2005-01-01), Allemang et al.
patent: 7027052 (2006-04-01), Thorn et al.
patent: 7035463 (2006-04-01), Monobe et al.
patent: 7363583 (2008-04-01), Costa
patent: 7593012 (2009-09-01), Ikehata et al.
patent: 2005/0094206 (2005-05-01), Tonisson
patent: 2005/0094207 (2005-05-01), Lo et al.
patent: 2005/0273730 (2005-12-01), Card et al.
patent: 2006/0294460 (2006-12-01), Chao et al.
Gansner, E. et al., “Drawing graphs with dot”, p. 1-40, Jan. 26, 2006.
Barth, W., M. Jünger, and P. Mutzel, 2002, Simple and efficient bilayer cross counting, Proc. 10th Int. Symposium of Graph Drawing, Lecture Notes in Computer Science 2528, pp. 130-141.
Brandes, U., and B. Köpf, Fast and simple horizontal coordinate assignment, Lecture Notes in Computer Science, Revised Papers from the 9th International Symposium on Graph Drawing, 2001, Springer-Verlag, pp. 31-44, vol. 2265.
Coffman E.G. Jr. and R.L. Graham, Optimal scheduling for two processor systems, Acta Informatica, 1972, pp. 200-213, vol. 1.
Duncan, C. A., M. T. Goodrich, and S. Kobourov, Balanced aspect ratio trees and their use for drawing very large graphs, Proceedings of the 6th Symposium on Graph Drawing, 1998, pp. 111-24, Springer-Verlag.
Eiglsperger, M., M. Siebenhaller, M. Kaufmann An efficient implementation of Sugiyama's algorithm for layered graph drawing, J. of Graph Algorithms and Applications, 2005, pp. 155-166, vol. 9, No. 3.
Gansner, E. R., E. Koutsofios, S.C. North, and K. P. Vo, A technique for drawing directed graphs, IEEE Trans. Soft. Eng., 1993, pp. 214-230, vol. 19.
Glee: Graph Layout Engine, available at http://research.microsoft.com/˜levnach/GLEEWebPage.htm.
Graphviz todo list Dec. 22, 2005, available at http://www.graphviz.org/doc/todo.html.
Katreniakova, J., Presentation of the content structurefor e-learning, written part of dissertation exam, Project of Dissertation Thesis, 2006, Bratislava.
Lutterkort, D., and J. Peters, Smooth paths in a polygonal channel, Proc. of the 15th Annual Symposium on Computational Geometry, 1999, pp. 316-321.
Myles, A., and J. Peters, Threading splines through 3D channels, Computer Aided Design, Feb. 2005, pp. 139-148, vol. 37, No. 2.
Nikolov, N. S., A. Tarassov, Graph layering by promotion of nodes, Discrete Applied Mathematics, Apr. 2006, vol. 154, No. 5, pp. 848-860.
Rowe, L. A., M. Davis, E. Messinger, C. Meyer, C. Spirakis, and A. Tuan, A browser for directed graphs, Software—Practice and Experience, 1987, vol. 17, No. 1, pp. 61-76.
Stedile, A., JMFGraph—A modular framework for drawing graphs in java, Master's Thesis, Graz Univ. of Tech., Institute for Info. Processing and Comp. Supported New Media (IICM), Nov. 18, 2001, Graz, Austria.

Affiliated with

Also associated with

Rating

Layered graph layouts with a given aspect ratio does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Layered graph layouts with a given aspect ratio, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Layered graph layouts with a given aspect ratio will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2654951