Maximizing the total resolution of graphs

DOI10.1007/978-3-642-18469-7_6MaRDI QIDQ3073659zbMATH OpenOpenAlexFDO

Authors Evmorfia N. Argyriou, Michael A. Bekos, Antonios Symvonis

Publication date 11 February 2011

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1009.2109

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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 to a common node (angular resolution) or by the angles formed at edge crossings (crossing resolution). In this paper, we evaluate both by introducing 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 drawing 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 (2-layered drawings). In addition, we present and experimentally evaluate a force-directed based algorithm that constructs drawings of large total resolution.

Recommendations

• Graphs with large total angular resolution
• A heuristic approach towards drawings of graphs with high crossing resolution
• Drawing Graphs in the Plane with High Resolution
• The crossing-angle resolution in graph drawing
• Circular graph drawings with large crossing angles

Cited in

(13)

• A heuristic approach towards drawings of graphs with high crossing resolution
• A greedy heuristic for crossing-angle maximization
• Right angle crossing graphs and 1-planarity
• The straight-line RAC drawing problem is NP-hard
• scientific article; zbMATH DE number 5001077 (Why is no real title available?)
• Vertex angle and crossing angle resolution of leveled tree drawings
• Angular Resolutions: Around Vertices and Crossings
• The stub resolution of 1-planar graphs
• Combinatorial properties and recognition of unit square visibility graphs
• Graphs with large total angular resolution
• Graphs with large total angular resolution
• Combinatorial properties and recognition of unit square visibility graphs
• Drawing graphs with right angle crossings

This page was built for publication: Maximizing the total resolution of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3073659)