LayoutImprovement

<<TableOfContents: execution failed [Argument "maxdepth" must be an integer value, not "[2]"] (see also the log)>>

Proposal

This RFC is meant to summarize and collect all ongoing layout improvement efforts and to provide a forum for new ideas.

Large Graph Layout

Cytoscape currently lacks the ability to layout graphs with large numbers of nodes and edges. Anything over 10,000 nodes and edges has the potential to become problematic. While speed if a concern, it appears the that more significant issue is memory consumption. Most layout algorithms simply allocate too much memory per graph object to function on normal workstations.

The initial goal of this effort should be the ability to layout a network with 100,000 nodes and edges in a small number of hours on an "average" workstation. Eventually, we would like to be able to increase this threshold by an order of magnitude.

Notes:

• Maybe implement the LGL algorithm, although it may be too slow for interactive use.

• Parallelize layout algorithms across multi-core CPUs?

• Investigate compressed graph in memory representations e.g. http://webgraph.dsi.unimi.it/

Interactive Layout

• Hub and spoke layout. Detect hubs and layout spokes around the hubs. Must evenly space nodes and prevent label overlapping. Also should optionally respect node attributes. This is one of the most common manual layout tasks biologists do. It is related to neighborhood layout in that it focuses on laying out small graphs.
• Neighborhood layout. This would focus on laying out just the immediate neighborhood of a node. A good use case is navigating interactions retrieved about a node from a database. This would also have to progressively layout more nodes as they are added to the neighborhood without changing the existing layout too much, so the user doesn't have to constantly get used to the positions of their favorite nodes.
• Bipartite circular layout - Layout a bipartite directed graph in concentric circles. An example of such a graph is a gene regulation network where nodes represent transcription factors and their targets.
• BioPAX ontology-based layout - BioPAX pathways represented in Cytoscape could be laid out based on templates that would recognize aspects of the biopax ontology to draw e.g. reactions in the standard way. Also, signaling pathways could be drawn from outside the cell to inside the cell. This would incorporate typical metabolic pathway layout algorithms. This is likely only easy to implement after BioPAX Level 3 is fully mapped to groups and hyperedges (~2008-2009).
• Dynamic interactive layout. Let the user layout, place and lock nodes as a force-directed dynamic layout is running.

MultiLevel Layout

See the MultilevelLayout page for details.

Biological Questions / Use Cases

Comments