A New Method for Efficiently Generating Planar Graph Visibility Representations

Boyer, John M. (2006) A New Method for Efficiently Generating Planar Graph Visibility Representations. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 508-511 (Official URL: http://dx.doi.org/10.1007/11618058_47).

Full text not available from this repository.

Abstract

A planar graph visibility representation maps each vertex to a horizontal segment at a vertical position and each edge to a vertical segment at a horizontal position such that each edge segment terminates at the vertical positions of its endpoint vertices and intersects no other horizontal vertex segments. [part of Introduction]

Item Type:Conference Poster
Additional Information:10.1007/11618058_47
Classifications:P Styles > P.900 Visibility
M Methods > M.600 Planar
P Styles > P.540 Planar
ID Code:727

Repository Staff Only: item control page

References

K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and Systems Sciences, 13:335-379, 1976.

J. Boyer and W. Myrvold. On the cutting edge: Simplified O(n) planarity by edge addition. Journal of Graph Algorithms and Applications, 8(3):241-273, 2004.

R. Jayakumar, K. Thulasiraman, and M. N. S. Swamy. Planar embedding: Linear-time algorithms for vertex placement and edge ordering. IEEE Transactions on Circuits and Systems, 35(3):334-344, 1988.

P. Rosenstiehl and R. Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete and Computational Geometry, 1(4):343-353, 1986.

R. Tamassia and I. G. Tollis. A unified approach to visibility representations of planar graphs. Discrete and Computational Geometry, 1(4):321-341, 1986.