fCoSE: A Fast Compound Graph Layout Algorithm with Constraint Support

Abstract

Visual analysis of relational information is vital in most real-life analytics applications. Automatic layout is a key requirement for effective visual display of such information. This article introduces a new layout algorithm named fCoSE for compound graphs showing varying levels of groupings or abstractions with support for user-specified placement constraints. fCoSE builds on a previous compound spring embedder layout algorithm and makes use of the spectral graph drawing technique for producing a quick draft layout, followed by phases where constraints are enforced and compound structures are properly shown while polishing the layout with respect to commonly accepted graph layout criteria. Experimental evaluation verifies that fCoSE produces quality layouts and is fast enough for interactive applications with small to medium-sized graphs by combining the speed of spectral graph drawing technique with the quality of force-directed layout algorithms while satisfying specified constraints and properly displaying compound structures. An implementation of fCoSE along with documentation and a demo page is freely available on GitHub at https://github.com/iVis-at-Bilkent/cytoscape.js-fcose.