Combining hierarchy and energy for drawing directed graphs
The DOI matches its Crossref record; 23 of the 24 references it cites were found in a registry or an index.
Abstract
We present an algorithm for drawing directed graphs which is based on rapidly solving a unique one-dimensional optimization problem for each of the axes. The algorithm results in a clear description of the hierarchy structure of the graph. Nodes are not restricted to lie on fixed horizontal layers, resulting in layouts that convey the symmetries of the graph very naturally. The algorithm can be applied without change to cyclic or acyclic digraphs and even to graphs containing both directed and undirected edges. We also derive a hierarchy index from the input digraph, which quantitatively measures its amount of hierarchy.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
Network motifs: simple building blocks of complex networks.
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002) · Science · doi:10.1126/science.298.5594.824 · Cited by 7,368
Graph drawing by force‐directed placement
Fruchterman, T. M. J., & Reingold, E. M. (1991) · Software: Practice and Experience · doi:10.1002/spe.4380211102 · Cited by 6,352
An algorithm for drawing general undirected graphs
Kamada, T., & Kawai, S. (1989) · Information Processing Letters · doi:10.1016/0020-0190(89)90102-6 · Cited by 2,698
Graph Drawing: Algorithms for the Visualization of Graphs
Battista, G. D., Eades, P., Tamassia, R., & Tollis, I. G. (1998) · Iris (Roma Tre University) · Cited by 1,977
Methods for Visual Understanding of Hierarchical System Structures
Sugiyama, K., Tagawa, S., & Toda, M. (1981) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/tsmc.1981.4308636 · Cited by 1,223
Eades, P. (1984) · Congressus Numerantium · Cited by 1,147
Tutte, W. T. (1963) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s3-13.1.743 · Cited by 1,114
A survey of graph layout problems
Díaz, J., Petit, J., & Serna, M. (2002) · ACM Computing Surveys · doi:10.1145/568522.568523 · Cited by 599
An r-Dimensional Quadratic Placement Algorithm
Hall, K. M. (1970) · Management Science · doi:10.1287/mnsc.17.3.219 · Cited by 522
Research works printed but not linked: 1
- 2003, The Matrix Market collection
Cited by
Whole-animal connectomes of both Caenorhabditis elegans sexes
Cook, S. J., Jarrell, T. A., Brittin, C. A., Wang, Y., Bloniarz, A. E., Yakovlev, M. A., Nguyen, K. C. Q., Tang, L. T.-H., Bayer, E. A., Duerr, J. S., et al. (2019) · Nature · doi:10.1038/s41586-019-1352-7 · Cited by 921
Structural Properties of the Caenorhabditis elegans Neuronal Network
Varshney, L. R., Chen, B. L., Paniagua, E., Hall, D. H., & Chklovskii, D. B. (2011) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1001066 · Cited by 867
The connectome of an insect brain
Winding, M., Pedigo, B. D., Barnes, C. L., Patsolic, H. G., Park, Y., Kazimiers, T., Fushiki, A., Andrade, I. V., Khandelwal, A., Valdes-Aleman, J., et al. (2023) · Science · doi:10.1126/science.add9330 · Cited by 435
Reading the Book of Memory: Sparse Sampling versus Dense Mapping of Connectomes
Seung, H. S. (2009) · Neuron · doi:10.1016/j.neuron.2009.03.020 · Cited by 153
Wang, Y., Wang, Y., Sun, Y., Zhu, L., Lu, K., Fu, C., Sedlmair, M., Deußen, O., & Chen, B. (2017) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2017.2745919 · Cited by 67
Metadata
- Authors
- Carmel, L., Harel, D., & Koren, Y.
- Affiliations
- Weizmann Institute of Science (IL)
- AT&T (United States) (US)
- ORCID
- Venue
- IEEE Transactions on Visualization and Computer Graphics
- Published
- 2004-01
- Volume
- 10
- Issue
- 1
- Pages
- 46-57
- ISSN
- 1077-2626 (ISSN-L)
- OpenAlex
- W2156458358
- Cited by
- 34
- References
- 24
- Citations by year
- 2026: 1 · 2025: 2 · 2024: 1 · 2023: 4 · 2022: 2 · 2021: 1 · 2019: 1 · 2017: 1 · 2015: 1 · 2014: 1 · 2013: 2
- FWCI
- 3.75
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Visualization and Computer Graphics (publishedVersion)
- PubMed (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Data Visualization and Analytics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
- Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Computer Graphics and Visualization Techniques
- Keywords
- graph layout algorithms, graph hierarchy, energy minimization, one-dimensional optimization, acyclic digraphs, graph symmetry
- MeSH terms
- Algorithms, Computer Graphics, Image Enhancement, Image Interpretation, Computer-Assisted, Paintings, Pattern Recognition, Automated, Signal Processing, Computer-Assisted, User-Computer Interface, Imaging, Three-Dimensional
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Combining hierarchy and energy for drawing directed graphs. https://app.cochat.ai/papers/10.1109/tvcg.2004.1260757
- The paper
- Carmel, L., Harel, D., & Koren, Y. (2004). Combining hierarchy and energy for drawing directed graphs. IEEE Transactions on Visualization and Computer Graphics. https://doi.org/10.1109/tvcg.2004.1260757
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.