Article

Scalable, versatile and simple constrained graph layout

Author:

Tim DwyerAuthors Info & Claims

EuroVis'09: Proceedings of the 11th Eurographics / IEEE - VGTC conference on Visualization

Pages 991 - 1006

Published: 10 June 2009 Publication History

Abstract

We describe a new technique for graph layout subject to constraints. Compared to previous techniques the proposed method is much faster and scalable to much larger graphs. For a graph with n nodes, m edges and c constraints it computes incremental layout in time O(n log n+m+c) per iteration. Also, it supports a much more powerful class of constraint: inequalities or equalities over the Euclidean distance between nodes. We demonstrate the power of this technique by application to a number of diagramming conventions which previous constrained graph layout methods could not support. Further, the constraint-satisfaction method-inspired by recent work in position-based dynamics--is far simpler to implement than previous methods.

References

[1]

BRANDES U., EIGLSPERGER M., KAUFMANN M., WAGNER D.: Sketch-driven orthogonal graph drawing. In Proc. of the 10th Intl. Symp. on Graph Drawing (GD'02) (2002), vol. 2528 of LNCS, Springer, pp. 1-11.

Digital Library

[2]

BÖRINGER K., PAULISCH F. N.: Using constraints to achieve stability in automatic graph layout algorithms. In Proc. of ACM Conf. on Human Factors in Computing Systems (1990), ACM, pp. 43-51.

Digital Library

[3]

BRANDES U., PICH C.: An experimental study on distance-based graph drawing. In Proc. 16th Intl. Symp. Graph Drawing (GD'08) (2009), vol. 5417, Springer, pp. 218-229.

Digital Library

[4]

DOBKIN D., HERSHBERGER J., KIRKPATRICK D., SURI S.: Computing the intersection-depth of polyhedra. Algorithmica 9 (1993), 518-533.

[5]

DWYER T., KOREN Y., MARRIOTT K.: IPSep-CoLa: an incremental procedure for separation constraint layout of graphs. IEEE Transactions on Visualization and Computer Graphics 12, 5 (2006), 821-828.

Digital Library

[6]

DWYER T., MARRIOTT K.: Constrained stress majorization using diagonally scaled gradient projection. In Proc. 15th Intl. Symp. Graph Drawing (GD '07) (2008), vol. 4875 of LNCS, Springer.

Digital Library

[7]

DWYER T., MARRIOTT K., SCHREIBER F., STUCKEY P. J., WOODWARD M., WYBROW M.: Exploration of networks using overview+detail with constraint-based cooperative layout. IEEE Transactions on Visualization and Computer Graphics 14, 6 (2008), 1293-1300.

Digital Library

[8]

DWYER T., MARRIOTT K., WYBROW M.: Dunnart: A constraint-based network diagram authoring tool. In Proc. 16th Intl. Symp. Graph Drawing (GD'08) (2009), vol. 5417 of LNCS, Springer, pp. 420-431.

Digital Library

[9]

DWYER T., MARRIOTT K., WYBROW M.: Topology preserving constrained graph layout. In Proc. 16th Intl. Symp. Graph Drawing (GD'08) (2009), vol. 5417 of LNCS, Springer, pp. 230-241.

Digital Library

[10]

EIGLSPERGER M., FÖSSMEIER U., KAUFMANN M.: Orthogonal graph drawing with constraints. In SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms (Philadelphia, PA, USA, 2000), Society for Industrial and Applied Mathematics, pp. 3-11.

Digital Library

[11]

HACHUL S., JÜNGER M.: An experimental comparison of fast algorithms for drawing general large graphs. In Proc. 13th Intl. Symp. on Graph Drawing (GD'05) (2005), vol. 3843 of LNCS, Springer, pp. 235-250.

Digital Library

[12]

HE W., MARRIOTT K.: Constrained graph layout. Constraints 3 (1998), 289-314.

Digital Library

[13]

HU Y.: Efficient and high quality force-directed graph drawing. The Mathematica Journal 10, 1 (2005), 37-71.

[14]

JAKOBSEN T.: Advanced character physics. In San Jose Games Developers' Conference (2001), www.gamasutra.com.

[15]

KAMADA T., KAWAI S.: An algorithm for drawing general undirected graphs. Inf. Process. Lett. 31, 1 (1989), 7-15.

Digital Library

[16]

LAUTHER U.: Multipole-based force approximation revisited - a simple but fast implementation using a dynamized enclosing-circle-enhanced k-d-tree. In Proc. 14th Intl. Symp. on Graph Drawing (GD'06) (2007), vol. 4372 of LNCS, pp. 20-29.

Digital Library

[17]

MERRICK D., DWYER T.: Skeletal animation for the exploration of graphs. In Australian Symp. on Information Visualisation 2004 (2004), vol. 35 of CRPIT, ACS, pp. 61-70.

Digital Library

[18]

MÜLLER M., HEIDELBERGER B., HENNIX M., RATCLIFF J.: Position based dynamics. In Proc. of Virtual Reality Interactions and Physical Simulations (VRIPhys) (2006), pp. 71-80.

[19]

MURRAY C., MERRICK D., TAKATSUKA M.: Graph interaction through force-based skeletal animation. In Australian Symp. on Information Visualisation 2004 (2004), vol. 35 of CRPIT, ACS, pp. 81-90.

Digital Library

[20]

NOCEDAL J., WRIGHT S. J.: Numerical Optimization, 2 ed. Springer Series in Operations Research. Springer, 2006.

[21]

RYALL K., MARKS J., SHIEBER S. M.: An interactive constraint-based system for drawing graphs. In ACM Symposium on User Interface Software and Technology (1997), pp. 97-104.

Digital Library

[22]

SUGIYAMA K., TAGAWA S., TODA M.: Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics 11, 2 (1981), 109-125.

Cited By

Devkota SAhmed RDe Luca FIsaacs KKobourov S(2019)Stress-Plus-X (SPX) Graph LayoutGraph Drawing and Network Visualization10.1007/978-3-030-35802-0_23(291-304)Online publication date: 17-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-35802-0_23
Wang YBaciu GLi CJohansson JSadlo FSchreck T(2018)Visualizing functional regions by analysis of geo-textual dataProceedings of the Eurographics/IEEE VGTC Conference on Visualization: Short Papers10.5555/3290776.3290782(25-29)Online publication date: 4-Jun-2018
https://dl.acm.org/doi/10.5555/3290776.3290782
Wang YBaciu GLi CKoyamada KRuchikachorn P(2017)Smooth animation of structure evolution in time-varying graphs with pattern matchingSIGGRAPH Asia 2017 Symposium on Visualization10.1145/3139295.3139302(1-8)Online publication date: 27-Nov-2017
https://dl.acm.org/doi/10.1145/3139295.3139302
Show More Cited By

Index Terms

Scalable, versatile and simple constrained graph layout

Recommendations

Constrained Graph Layout

Most current graph layout technology does not lend itself to interactive applications such as animation or advanced user interfaces. We introduce the constrained graph layout model which is better suited for interactive applications. In this model, input ...
Topology Preserving Constrained Graph Layout
Graph Drawing

Constrained graph layout is a recent generalisation of force-directed graph layout which allows constraints on node placement. We give a constrained graph layout algorithm that takes an initial feasible layout and improves it while preserving the ...
Queue Layout of Bipartite Graph Subdivisions

For an integer d > 0, a d-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into d sets of non-nested edges with respect to the vertex ordering. Recently V. Dujmović and D. R. Wood showed that for every ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EuroVis'09: Proceedings of the 11th Eurographics / IEEE - VGTC conference on Visualization

June 2009

1054 pages

Editors:
Hans-Christian Hege
Zuse Institute Berlin, Germany
,
Ingrid Hotz
Zuse Institute Berlin, Germany
,
Tamara Munzner
University of British Columbia, Canada

Sponsors

ZIB: ZIB
IEEE VGTC: IEEE Visualization and Graphics Technical Committee
DFG Research Center Matheon: DFG Research Center Matheon
NVIDIA
EUROGRAPHICS: The European Association for Computer Graphics

Publisher

The Eurographs Association & John Wiley & Sons, Ltd.

Chichester, United Kingdom

Publication History

Published: 10 June 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Devkota SAhmed RDe Luca FIsaacs KKobourov S(2019)Stress-Plus-X (SPX) Graph LayoutGraph Drawing and Network Visualization10.1007/978-3-030-35802-0_23(291-304)Online publication date: 17-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-35802-0_23
Wang YBaciu GLi CJohansson JSadlo FSchreck T(2018)Visualizing functional regions by analysis of geo-textual dataProceedings of the Eurographics/IEEE VGTC Conference on Visualization: Short Papers10.5555/3290776.3290782(25-29)Online publication date: 4-Jun-2018
https://dl.acm.org/doi/10.5555/3290776.3290782
Wang YBaciu GLi CKoyamada KRuchikachorn P(2017)Smooth animation of structure evolution in time-varying graphs with pattern matchingSIGGRAPH Asia 2017 Symposium on Visualization10.1145/3139295.3139302(1-8)Online publication date: 27-Nov-2017
https://dl.acm.org/doi/10.1145/3139295.3139302
Dragoni MTonelli SMoretti G(2017)A Knowledge Management Architecture for Digital Cultural HeritageJournal on Computing and Cultural Heritage 10.1145/301228910:3(1-18)Online publication date: 28-Jul-2017
https://dl.acm.org/doi/10.1145/3012289
Bespinyowong RChen WJagadish HMa Y(2016)ExRankProceedings of the VLDB Endowment10.14778/3007263.30073019:13(1529-1532)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.14778/3007263.3007301
Muelder CFaris RMa KAnjum AZhao X(2016)A visual analytics approach to author name disambiguationProceedings of the 3rd IEEE/ACM International Conference on Big Data Computing, Applications and Technologies10.1145/3006299.3006302(52-60)Online publication date: 6-Dec-2016
https://dl.acm.org/doi/10.1145/3006299.3006302
Fried ODiVerdi SHalber MSizikova EFinkelstein A(2015)IsoMatchComputer Graphics Forum10.1111/cgf.1254934:2(155-166)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1111/cgf.12549
Gretarsson BO’Donovan JBostandjiev SHöllerer TAsuncion ANewman DSmyth P(2012)TopicNetsACM Transactions on Intelligent Systems and Technology10.1145/2089094.20890993:2(1-26)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1145/2089094.2089099
Simonetto PArchambault DAuber DBourqui R(2011)ImPrEdProceedings of the 13th Eurographics / IEEE - VGTC conference on Visualization10.1111/j.1467-8659.2011.01956.x(1071-1080)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1111/j.1467-8659.2011.01956.x
Myers CDuke DTelea AGörg CReiss S(2010)A map of the heapProceedings of the 5th international symposium on Software visualization10.1145/1879211.1879223(63-72)Online publication date: 25-Oct-2010
https://dl.acm.org/doi/10.1145/1879211.1879223
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents