2-Visibility Drawings of Planar Graphs

Fößmeier, Ulrich and Kant, Goos and Kaufmann, Michael (1997) 2-Visibility Drawings of Planar Graphs. In: Symposium on Graph Drawing, GD '96 , September 18-20, 1996, Berkeley, California, USA , pp. 155-168 (Official URL: http://dx.doi.org/10.1007/3-540-62495-3_45).

Full text not available from this repository.

Abstract

In a 2-visibility drawing the vertices of a given graph are represented by rectangular boxes and the adjacency relations are expressed by horizontal and vertical lines drawn between the boxes. In this paper we want to emphasize this model as a practical alternative to other representations of graphs, and to demonstrate the quality of the produced grawings. We give several approaches, heuristics as well as provably good algorithms, to represent planar graphs within this model. To this, we present a polynomial time algorithm to compute a band-minimum orthogonal drawing under the restriction that the number of bends at each edge is at most 1.

Item Type:Conference Paper
Additional Information:10.1007/3-540-62495-3_45
Classifications:P Styles > P.900 Visibility
G Algorithms and Complexity > G.210 Bends
P Styles > P.540 Planar
ID Code:63

Repository Staff Only: item control page

References

Biedl T. and G. Kant, A better heuristik for orthogonal graph drawings, Proc. 2nd Ann. European Symposium of Algorithms (ESA '94), LNCS 855, Springer-Verlag, pp. 24-35, 1994.

Chrobak M. and T. H. Payne, A linear time algorithm for drawing planar graphs on the grid, Tech. report UCR-CS-90-2, Dept. of Math. and Comp. Science, University of California at Riverside, 1990.

Di Battista G., P. Eades, R. Tamassia and I. G. Tollis, Algorithms for automatic graph drawing: an annotated bibliography, Computational Geom.: Theory and Practice 4, pp. 235-282, 1994.

Fraysseix, H. de, J. Pach and R. Pollack, How to draw a planar graph on a grid, Combinatorica 10, pp. 41-51, 1990.

Fößmeier, U., and M. Kaufmann, Drawing high degree graphs with low bend numbers, Proc. 4th Symposium on Graph Drawing (GD '95), LNCS 1027, Springer-Verlag, pp. 254-266, 1995.

Hutchinson, J. P., T. Shermer and A. Vince, On representation of some thickness-two graphs, Proc. 4th Symposium on Graph Drawing (GD '95), LNCS 1027, Springer-Verlag, pp. 324-332, 1996.

Kant, G., A more compact visibility representation, Proc. 19th Intern. Workshop on Graph-Theoretic Concepts in Comp. Science (WG '93), LNCS 790, Springer-Verlag, pp. 411-424, 1994.

Kant, G., and X. He, two algorithms for finding rectangular duals of planar graphs, Proc. 19th Intern. Workshop on Graph-Theoretic Concepts in Comp. Science (WG '93), LNCS 790, Springer-Verlag, pp. 396-410, 1994.

Kirkpatrick, D. G., and S. K. Wismath, Weighted visibility graphs of bars and related flow problems, Proc. 1st Workshop Algorithms Data Structures (WADS '89), LNCS 382, Springer-Verlag, pp. 325-334, 1989.

Mutzel, P., The Maximum Planar Subgraph Problem, Doctoral Dissertation, Köln 1994.

Papakostas A. and I. G. Tollis, Improved algorithms and bounds for orthogonal drawings, Proc. DIMACS Workshop on Graph Drawing (GD '94), LNCS 894, Springer-Verlag, pp. 40-51, 1994.

Rosenstiehl, P., and R. E. Tarjan, Rectilinear planar layouts and bipolar orientations of planar graphs, Discrete Comput. Geom. 1, pp. 343-353, 1986.

Tamassia R., On embedding a graph in the grid with the minimum number of bends, SIAM Journal of Computing 16, pp. 421-444, 1987.

Tamassia, R., G. Di Battista and C. Batini, Automatic graph drawing and readability of diagrams, IEEE Trns. of Systems, Man and Cybern. 18, pp. 61-79, 1988.

Tamassia R. and I. Tollis, A unified approach to visibility representations of planar graphs, Discrete and Comp. Geom. 1, pp. 321-341, 1986.

Tamassia R. and I. Tollis, Efficient embedding of planar graphs in linear time, in Proc. IEEE Int. Symp. on Circuit and Systems, Philadelphia, pp. 495-498, 1987.

Thomassen C., Rectilinear drawings of graphs, J. Graph Theory 12, pp.335-341, 1988.

Wismath S. K., Charakterizing bar line-of-sight graphs, Proc. 1st Annual ACM Symp. on Computational Geometry, pp. 147-152, 1985.