Maximizing the Total Resolution of Graphs

A major factor affecting the readability of a graph drawing is its resolution. In the graph drawing literature, the resolution of a drawing is either measured based on the angles formed by consecutive edges incident on a common vertex (angular resolution) or by the angles formed at edge crossings (c...

Full description

Saved in:
Bibliographic Details
Published in:Computer journal 2013-07, Vol.56 (7), p.887-900
Main Authors: Argyriou, EN, Bekos, MA, Symvonis, A
Format: Article
Language:English
Subjects:
Algorithms
Angular resolution
Asymptotic properties
Computer science
Construction
Graph algorithms
Graph representations
Graphs
Optimization
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A major factor affecting the readability of a graph drawing is its resolution. In the graph drawing literature, the resolution of a drawing is either measured based on the angles formed by consecutive edges incident on a common vertex (angular resolution) or by the angles formed at edge crossings (crossing resolution). In this paper, we introduce the notion of 'total resolution', that is, the minimum of the angular and crossing resolution. To the best of our knowledge, this is the first time where the problem of maximizing the total resolution of a graph over all its drawings is studied. The main contribution of the paper consists of drawings of asymptotically optimal total resolution for complete graphs (circular drawings) and for complete bipartite graphs (two-layered drawings). In addition, we present and experimentally evaluate a force-directed-based algorithm that constructs drawings of large total resolution.
ISSN:0010-4620
1460-2067
DOI:10.1093/comjnl/bxs088