- 著者
- M. Formann, T. Hagerup, J. Haralambides, M., Kaufmann, M. Kaufmann
- タイトル
- Drawing graphs in the plane with high resolution
- 書籍
- Proceedings of 31st Annual Symposium on Foundations
of Computer Science
- ページ
- 86-95
- 日時
- October 1990
- 概要
- The problem of drawing a graph in the plane so that
edges appear as straight lines and the minimum angle
formed by any pair of incident edges is maximized is
studied. The resolution of a layout is defined to be
the size of the minimum angle formed by incident
edges of the graph, and the resolution of a graph is
defined to be the maximum resolution of any layout
of the graph. The resolution R of a graph is
characterized in terms of the maximum node degree d
of the graph by proving that Omega (1/d/sup
2/)
- カテゴリ
- GraphLayout

Category: GraphLayout
Organization: F.T.; Simvonis, A.; Welzl, E.; Woeginger, G.
Fachbereich Math., Freie University Berlin, West
Germany
Abstract: The problem of drawing a graph in the plane so that
edges appear as straight lines and the minimum angle
formed by any pair of incident edges is maximized is
studied. The resolution of a layout is defined to be
the size of the minimum angle formed by incident
edges of the graph, and the resolution of a graph is
defined to be the maximum resolution of any layout
of the graph. The resolution R of a graph is
characterized in terms of the maximum node degree d
of the graph by proving that Omega (1/d/sup
2/)<or=R<or=2 pi /d for any graph. Moreover, it is
proved that R= Theta (1/d) for many graphs,
including planar graphs, complete graphs,
hypercubes, multidimensional meshes and tori, and
other special networks. It is also shown that the
problem of deciding if R=2 pi /d for a graph is
NP-hard for d=4, and a counting argument is used to
show that R=O(log d/d/sup 2/) for many graphs
Number: 90
Bibtype: InProceedings
Booktitle: Proceedings of 31st Annual Symposium on Foundations
of Computer Science
Author: M. Formann
T. Hagerup
J. Haralambides
M.
Kaufmann
M. Kaufmann
Pages: 86-95
Month: oct
Title: Drawing graphs in the plane with high resolution
Year: 1990
Volume: 1
Keyword: graph theory, optimisation, high resolution planar
graph drawing, straight line edges, NP-hard problem,
minimum angle, incident edges, maximum node degree,
complete graphs, hypercubes, multidimensional
meshes, tori, counting