Drawing graphs in the plane with high resolution
- 1 January 1990
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
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/)Keywords
This publication has 6 references indexed in Scilit:
- On Embedding a Graph in the Grid with the Minimum Number of BendsSIAM Journal on Computing, 1987
- Rectilinear planar layouts and bipolar orientations of planar graphsDiscrete & Computational Geometry, 1986
- A framework for solving VLSI graph layout problemsJournal of Computer and System Sciences, 1984
- A polynomial algorithm for the MIN CUT linear arrangement of treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Universality considerations in VLSI circuitsIEEE Transactions on Computers, 1981
- The NP-Completeness of the bandwidth minimization problemComputing, 1976