Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(6)
Call Graph
Directed Graph
Graph Layout
Side Effect
Software Configuration Management
Software Systems
Related Publications
(5)
cluster analysis for applications
A framework for selective recompilation in the presence of complex intermodule dependencies
Automatic Graph Clustering
Visualization of structural information: automatic drawing of compound digraphs
Generalized Fisheye Views of Graphs
Subscribe
Academic
Publications
Edge concentration: a method for clustering directed graphs
Edge concentration: a method for clustering directed graphs,10.1145/73337.73350,ACM Sigsoft Software Engineering Notes,Frances J. Newbery
Edit
Edge concentration: a method for clustering directed graphs
(
Citations: 27
)
BibTex

RIS

RefWorks
Download
Frances J. Newbery
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 &Ogr;(n4) 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.
Journal:
ACM Sigsoft Software Engineering Notes
, vol. 14, no. 7, pp. 7685, 1989
DOI:
10.1145/73337.73350
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
portal.acm.org
)
(
www.informatik.unitrier.de
)
(
portal.acm.org
)
(
portal.acm.org
)
(
portal.acm.org
)
More »
Citation Context
(15)
...Initially, edge bundling was proposed for circular and hierarchical layout [7,12,21,
22
], and was later extended to general graph layouts [5,13,18]...
...Newbery [
22
] proposed a method for handling layered layouts of directed graphs...
Emden R. GansnerYifan
,
et al.
Multilevel agglomerative edge bundling for visualizing large graphs
...One of the popular methods to improve quality of such drawings is edge bundling [
13
,9,7,3]...
...bundling is related to edge concentration [
13
], where a twolayered graph is covered by bicliques reducing the number of drawn edges...
Sergey Pupyrev
,
et al.
Improving Layered Graph Layouts with Edge Bundling
...The graph edge density can be alleviated by magnifying the congestion regions [2,5,6,10], merging and rearranging edges [3,4,
12
]...
...NewBery [
12
] proposed the Edge Concentration method which reduces the number of edges while retaining the graph structural information...
Hong Zhou
,
et al.
EnergyBased Hierarchical Edge Clustering of Graphs
...In previous studies a method of increasing the resolution of the display device and creating a very detailed drawing [5] was used, as well as a method of collecting several nodes and drawing them as one node [6,
7
]...
Shuji Sato
,
et al.
Readable Representations for LargeScale Bipartite Graphs
...We are aware of the Edge Concentration method by Newbery [
21
]...
...Fig. 6. Confluent drawing for examples of Newbery [
21
]...
David Eppstein
,
et al.
Confluent Layered Drawings
References
(10)
Discovering, visualizing, and controlling software structure
(
Citations: 32
)
R. W. Schwanke
,
R. Z. Altucher
,
M. A. Platoff
Journal:
ACM Sigsoft Software Engineering Notes
, vol. 14, no. 3, pp. 147154, 1989
An Analysis of Some Graph Theoretical Cluster Techniques
(
Citations: 109
)
J. Gary Augustson
,
Jack Minker
Journal:
Journal of The ACM  JACM
, vol. 17, no. 4, pp. 571588, 1970
Cross references are features
(
Citations: 40
)
Robert W. Schwanke
,
Michael A. Platoff
Journal:
ACM Sigsoft Software Engineering Notes
, vol. 14, no. 7, pp. 8695, 1989
Covering edges by cliques with regard to keyword conflicts and intersection graphs
(
Citations: 37
)
Lawrence T. Kou
,
Larry J. Stockmeyer
,
C. K. Wong
Journal:
Communications of The ACM  CACM
, vol. 21, no. 2, pp. 135139, 1978
System Structure Analysis: Clustering with Data Bindings
(
Citations: 193
)
David H. Hutchens
,
Victor R. Basili
Journal:
IEEE Transactions on Software Engineering  TSE
, vol. 11, no. 8, pp. 749757, 1985
Sort by:
Citations
(27)
Multilevel agglomerative edge bundling for visualizing large graphs
(
Citations: 3
)
Emden R. GansnerYifan
,
Yifan Hu
,
Stephen North
,
Carlos Scheidegger
Conference:
Visualization Symposium, Pacific AsiaPacific  formerly AsiaPacific APVIS
, 2011
Improving Layered Graph Layouts with Edge Bundling
(
Citations: 2
)
Sergey Pupyrev
,
Lev Nachmanson
,
Michael Kaufmann
Conference:
Symposium on Graph Drawing  GD
, pp. 329340, 2010
EnergyBased Hierarchical Edge Clustering of Graphs
(
Citations: 4
)
Hong Zhou
,
Xiaoru Yuan
,
Weiwei Cui
,
Huamin Qu
,
Baoquan Chen
Conference:
Visualization Symposium, Pacific AsiaPacific  formerly AsiaPacific APVIS
, pp. 5561, 2008
Readable Representations for LargeScale Bipartite Graphs
(
Citations: 1
)
Shuji Sato
,
Kazuo Misue
,
Jiro Tanaka
Conference:
KnowledgeBased Intelligent Information & Engineering Systems  KES
, pp. 831838, 2008
Confluent Layered Drawings
(
Citations: 3
)
David Eppstein
,
Michael T. Goodrich
,
Jeremy Yu Meng
Journal:
Algorithmica
, vol. 47, no. 4, pp. 439452, 2007