Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
3.7
2.3
Journals
Algorithms
Special Issues
Graph Drawing and Experimental Algorithms
share announcement

Graph Drawing and Experimental Algorithms

A special issue of Algorithms (ISSN 1999-4893).

Deadline for manuscript submissions: closed (20 December 2015) | Viewed by 21602

Special Issue Editor

Prof. Dr. Maurizio Patrignani

E-Mail Website
Guest Editor
Department of Engineering, Roma Tre University, Via della Vasca Navale, 79, 00146 Rome, Italy
Interests: algorithm engineering; graph drawing; network visualization; computer networks
Special Issues, Collections and Topics in MDPI journals

Special Issue Information

Dear Colleagues,

Graph drawing concerns the visualization of graphs and networks and is motivated by those application domains where it is crucial to visually analyse and interact with relational datasets. Examples include social sciences, Internet and web computing, information systems, computational biology, networking, VLSI circuit design, and software engineering.

Algorithmic experiments have been considered as integral aspects of graph drawing from its very inception and are indispensable when it comes to developing practically relevant algorithms.

The main theme of this Special Issue is the role of experimentation and of algorithm engineering techniques in the design and evaluation of graph drawing algorithms and graph visualization tools. Submissions should present significant contributions supported by experimental evaluation and methodological issues in the design and interpretation of experiments, or application-driven case studies that deepen the understanding of graph drawing complexity and of the scalability of the proposed solutions and heuristics.

Maurizio Patrignani
Guest Editor

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Algorithms is an international peer-reviewed open access monthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 1600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Keywords

  • algorithms and data structures for graph and network visualization
  • implementation and experimentation of graph drawing algorithms
  • experimental evaluation of graph visualization libraries and tools
  • usability assessment of exact and heuristic solutions to graph visualization problems

Published Papers (3 papers)

Download All Papers
Order results
Result details
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:

Research

14805 KiB  
Article
Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition
by Fabian Lipp, Alexander Wolff and Johannes Zink
Algorithms 2016, 9(3), 53; https://0-doi-org.brum.beds.ac.uk/10.3390/a9030053 - 04 Aug 2016
Cited by 4 | Viewed by 8346
Abstract
The force-directed paradigm is one of the few generic approaches to drawing graphs. Since force-directed algorithms can be extended easily, they are used frequently. Most of these algorithms are, however, quite slow on large graphs, as they compute a quadratic number of forces [...] Read more.
The force-directed paradigm is one of the few generic approaches to drawing graphs. Since force-directed algorithms can be extended easily, they are used frequently. Most of these algorithms are, however, quite slow on large graphs, as they compute a quadratic number of forces in each iteration. We give a new algorithm that takes only O ( m + n log n ) time per iteration when laying out a graph with n vertices and m edges. Our algorithm approximates the true forces using the so-called well-separated pair decomposition. We perform experiments on a large number of graphs and show that we can strongly reduce the runtime, even on graphs with less than a hundred vertices, without a significant influence on the quality of the drawings (in terms of the number of crossings and deviation in edge lengths). Full article
(This article belongs to the Special Issue Graph Drawing and Experimental Algorithms)
►▼ Show Figures

Graphical abstract

668 KiB  
Article
Modifying Orthogonal Drawings for Label Placement
by Konstantinos G. Kakoulis and Ioannis G. Tollis
Algorithms 2016, 9(2), 22; https://0-doi-org.brum.beds.ac.uk/10.3390/a9020022 - 28 Mar 2016
Cited by 1 | Viewed by 6154
Abstract
In this paper, we investigate how one can modify an orthogonal graph drawing to accommodate the placement of overlap-free labels with the minimum cost (i.e., minimum increase of the area and preservation of the quality of the drawing). We investigate computational [...] Read more.
In this paper, we investigate how one can modify an orthogonal graph drawing to accommodate the placement of overlap-free labels with the minimum cost (i.e., minimum increase of the area and preservation of the quality of the drawing). We investigate computational complexity issues of variations of that problem, and we present polynomial time algorithms that find the minimum increase of space in one direction, needed to resolve overlaps, while preserving the orthogonal representation of the orthogonal drawing when objects have a predefined partial order. Full article
(This article belongs to the Special Issue Graph Drawing and Experimental Algorithms)
►▼ Show Figures

Figure 1

1137 KiB  
Article
Generating Realistic Labelled, Weighted Random Graphs
by Michael Charles Davis, Zhanyu Ma, Weiru Liu, Paul Miller, Ruth Hunter and Frank Kee
Algorithms 2015, 8(4), 1143-1174; https://0-doi-org.brum.beds.ac.uk/10.3390/a8041143 - 08 Dec 2015
Cited by 1 | Viewed by 6283
Abstract
Generative algorithms for random graphs have yielded insights into the structure and evolution of real-world networks. Most networks exhibit a well-known set of properties, such as heavy-tailed degree distributions, clustering and community formation. Usually, random graph models consider only structural information, but many [...] Read more.
Generative algorithms for random graphs have yielded insights into the structure and evolution of real-world networks. Most networks exhibit a well-known set of properties, such as heavy-tailed degree distributions, clustering and community formation. Usually, random graph models consider only structural information, but many real-world networks also have labelled vertices and weighted edges. In this paper, we present a generative model for random graphs with discrete vertex labels and numeric edge weights. The weights are represented as a set of Beta Mixture Models (BMMs) with an arbitrary number of mixtures, which are learned from real-world networks. We propose a Bayesian Variational Inference (VI) approach, which yields an accurate estimation while keeping computation times tractable. We compare our approach to state-of-the-art random labelled graph generators and an earlier approach based on Gaussian Mixture Models (GMMs). Our results allow us to draw conclusions about the contribution of vertex labels and edge weights to graph structure. Full article
(This article belongs to the Special Issue Graph Drawing and Experimental Algorithms)
►▼ Show Figures

Graphical abstract

Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
 
Displaying articles 1-3
Back to TopTop