Article

Free access

Edge concentration: a method for clustering directed graphs

Author:

F. J. NewberyAuthors Info & Claims

SCM '89: Proceedings of the 2nd International Workshop on Software configuration management

Pages 76 - 85

https://doi.org/10.1145/72910.73350

Published: 01 October 1989 Publication History

PDF eReader

Abstract

The display of a directed graph is a commonly used visual aid for representing relationships. However, some graphs contain so many edges that their display by traditional graph layout algorithms is virtually impossible because of the overwhelming number of crossings. Graphs representing large software systems and their configurations are particularly prone to this problem. Examples of such graphs include: graphs depicting a system's configuration, call graphs, graphs depicting import and export relationships between modules, and graphs depicting the “includes” relation among a system's source files.

This paper proposes the elimination of some edges by replacing sets of edges that have the same set of source and target nodes by a special node called an edge concentration node. Reducing the number of edges often has the desirable side effect of reducing the number of crossings. An algorithm that determines a reasonable set of edge concentrations of a graph in Ο(n₄) operations for each level in the graph is presented where n is the number of nodes in that level. Several examples from the area of software configuration management are shown to demonstrate the effectiveness of using edge concentrations.

References

[1]

J. Gary Augustson and Jack blinker. An analysis of some graph theoretical cluster techniques. Journal of the ACM, 17(4):571- 588, October 1970.

Digital Library

Google Scholar

[2]

L. A. Belady and C. J. Evangelisti. System Partitioning and Its ikleasure. Technical Report Research Report RC 7560, IBM, March 1979.

Google Scholar

[3]

Michael R. Garey and David S. Johnson. Computers and Intractability - A Guide to the Theory of hTP-Completeness. W. II. Freeman and Company, 1979.

Digital Library

Google Scholar

[4]

David II. Rutchens and Victor R. Basili. System structure analysis: clustering with data bindings. IEEE Transactions on Software Engineering, SE-11(8):749-757, August 1985.

Digital Library

Google Scholar

[5]

Ian Holyer. The NP-Completeness of some edge partition problems. SIAM J. Computing, 10(4):713-717, November 1981.

Crossref

Google Scholar

[6]

L.T. Kou, L.J. Stockmeyer, and C.K. Wang. Covering edges by cliques with regards to keyword conflicts and intersection graphs. Communications of the ACM, 21(2):135-139, February 197s.

Digital Library

Google Scholar

[7]

Eli Benjamin Messinger. A,atomatic Layozlt of Large Directed Graphs. PhD thesis, University of Washington, Department of Computer Sciences, July 1%X. TR Number SS- 07-08.

Google Scholar

[8]

Frances J. Newbery. EDGE: An Extendible Directed Graph Editor. Technical Report S/M, University of Iiarlsruhe, Department of Informatics, June 1988.

Google Scholar

[9]

R. TV. Schwanke, R. Z. Altucher, and M. A. Platoff. Discovering, visualizing, and controlling software structure. In Proceedings of the Fifth International Workshop on Software Specification and Design, pages 147- 150, Pittsburgh, P-4, May 19-20 1989. ACM SIGSOFT Engineering Notes, Volume 14, Number 3.

Digital Library

Google Scholar

[10]

Robert TV. Schwanke and Michael A. Platoff. Cross references are features. In Proceedings of the Second International Workshop on Software Configuration Management, Princeton, NJ, Oct. 2427 1989.

Digital Library

Google Scholar

[11]

Kozo Sugiyama, Shojiro Tagawa, and Mitsuhiko Toda. Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, hfan, and Cybernetics, SAIC-11(2):109-125. February 1981.

Google Scholar

Cited By

View all

Meikari JSaga R(2022)Evolutionary Node Layout and Edge Bundling2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870416(1-6)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1109/CEC55065.2022.9870416
Bhavsar SPatil VPatil A(2022)Graph partitioning and visualization in graph mining: a surveyMultimedia Tools and Applications10.1007/s11042-022-13017-581:30(43315-43356)Online publication date: 23-May-2022
https://doi.org/10.1007/s11042-022-13017-5
Eades PKlein K(2018)Graph VisualizationGraph Data Management10.1007/978-3-319-96193-4_2(33-70)Online publication date: 1-Nov-2018
https://doi.org/10.1007/978-3-319-96193-4_2
Show More Cited By

Index Terms

Edge concentration: a method for clustering directed graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
  2. Mathematical analysis
    1. Functional analysis
      1. Approximation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

Edge concentration: a method for clustering directed graphs

The display of a directed graph is a commonly used visual aid for representing relationships. However, some graphs contain so many edges that their display by traditional graph layout algorithms is virtually impossible because of the overwhelming number ...
On antimagic directed graphs

An antimagic labeling of an undirected graph G with n vertices and m edges is a bijection from the set of edges of G to the integers {1, …, m} such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges ...
2-Edge Connectivity in Directed Graphs

Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly, not much has been investigated for directed graphs. In this article, we study 2-edge ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCM '89: Proceedings of the 2nd International Workshop on Software configuration management

October 1989

178 pages

ISBN:0897913345

DOI:10.1145/72910

Editor:
Richard N. Taylor
Univ. of California, Irvine

ACM SIGSOFT Software Engineering Notes Volume 14, Issue 7
Nov. 1989
178 pages
ISSN:0163-5948
DOI:10.1145/73337
Editor:
Richard N. Taylor
Univ. of Calfornia, Irvine
Issue’s Table of Contents

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1989

Check for updates

Qualifiers

Article

Conference

SCM

Sponsor:

SIGSOFT
IEEE-CS\TCSE

SCM: 2nd Intl Workshop on Software Configuration Mgmt.

October 24 - 27, 1989

New Jersey, Princeton, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
1,019
Total Downloads

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

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Meikari JSaga R(2022)Evolutionary Node Layout and Edge Bundling2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870416(1-6)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1109/CEC55065.2022.9870416
Bhavsar SPatil VPatil A(2022)Graph partitioning and visualization in graph mining: a surveyMultimedia Tools and Applications10.1007/s11042-022-13017-581:30(43315-43356)Online publication date: 23-May-2022
https://doi.org/10.1007/s11042-022-13017-5
Eades PKlein K(2018)Graph VisualizationGraph Data Management10.1007/978-3-319-96193-4_2(33-70)Online publication date: 1-Nov-2018
https://doi.org/10.1007/978-3-319-96193-4_2
(2016)Edge routing with ordered bundlesComputational Geometry: Theory and Applications10.1016/j.comgeo.2015.10.00552:C(18-33)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.comgeo.2015.10.005
Nikolov N(2016)Sugiyama AlgorithmEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_649(2162-2166)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_649
Nikolov N(2015)Sugiyama AlgorithmEncyclopedia of Algorithms10.1007/978-3-642-27848-8_649-1(1-6)Online publication date: 24-Jan-2015
https://doi.org/10.1007/978-3-642-27848-8_649-1
Nguyen QEades PHong S(2013)On the faithfulness of graph visualizations2013 IEEE Pacific Visualization Symposium (PacificVis)10.1109/PacificVis.2013.6596147(209-216)Online publication date: Feb-2013
https://doi.org/10.1109/PacificVis.2013.6596147
Pupyrev SNachmanson LKaufmann M(2011)Improving Layered Graph Layouts with Edge BundlingGraph Drawing10.1007/978-3-642-18469-7_30(329-340)Online publication date: 2011
https://doi.org/10.1007/978-3-642-18469-7_30
Pupyrev SNachmanson LKaufmann M(2010)Improving layered graph layouts with edge bundlingProceedings of the 18th international conference on Graph drawing10.5555/1964371.1964402(329-340)Online publication date: 21-Sep-2010
https://dl.acm.org/doi/10.5555/1964371.1964402
Zhou HYuan XCui WQu HChen B(2008)Energy-Based Hierarchical Edge Clustering of Graphs2008 IEEE Pacific Visualization Symposium10.1109/PACIFICVIS.2008.4475459(55-61)Online publication date: Mar-2008
https://doi.org/10.1109/PACIFICVIS.2008.4475459
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Edge concentration: a method for clustering directed graphs

On antimagic directed graphs

2-Edge Connectivity in Directed Graphs