Regular Edge Labelings and Drawings of Planar Graphs

He, Xin and Kao, Ming-Yang (1995) Regular Edge Labelings and Drawings of Planar Graphs. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 96-103 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_360).

Full text not available from this repository.

Abstract

The problems of nicely drawing planar graphs have received increasing attention due to their broad applications [5]. A technique, regular edge labeling, was successfully used in solving several planar graph drawing problems, including visibility representation, straight-line embedding, and rectangular dual problems. A regular edge labeling of a plane graph G labels the edges of G so that the edge labels around any vertex show certain regular pattern. The drawing of G is obtained by using the combinatorial structures resulting from the edge labeling. In this paper, we survey these drawing algorithms and discuss some open problems.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_360
Classifications:M Methods > M.600 Planar
G Algorithms and Complexity > G.630 Labeling
A General Literature > A.001 Introductory and Survey
P Styles > P.540 Planar
ID Code:102

Repository Staff Only: item control page

References

J. Bhasker and S. Sahni, A linear algorithm to check for the existence of a rectangular dual of a planar triangulated graph, Networks 17, 1987, pp. 307-317.

J. Bhasker and S. Sahni, A linear algorithm to find a rectangular dual of a planar triangulated graph, Algorithmica 3 , 1988, pp. 247-278.

N. Chiba, T. Yamanouchi, and T. Nishizeki, Linear algorithms for convex drawings of planar graphs, in Progress in Graph Theory, 1982, pp. 153-173.

M. Chrobak and T.H. Payne, A linear time algorithm for drawing planar graphs on a grid, TR. UCR-CS-90-2, Dept. of Math. and CS., Univ. of Calif. ad Riverside.

P. Eades and R. Tamassia, Algorithms for automatic graph drawing: an annotated bibliography, TR., Dept. of Comp. Sci., Brown Univ., 1993.

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

H. de Fraysseix, J. Pach and R. Pollack, Small sets supporting Fáry embeddings of planar graphs, Proc. of the 20th ACM STOC, 1988, pp. 426-433.

I. Fáry, On straight line representation of planar graphs, Acta Sci Math Szeged, 11 (1948), pp. 229-233.

M. Fürer, X. He, M.Y. Kao, and B.Raghavachari, 0(n log logn)-work parallel algorithms for straight-line grid embeddings of planar graphs, Proc. of 4th ACM SPAA, 1992, pp. 410-419. Improved version to appear in SIAM J. Discrete Math.

X. He, On finding the rectangular duals of planar triangulated graphs, SIAM J. Comput. 22 (6), 1993, pp. 1218-1226.

X. He, An efficient parallel algorithm for finding rectangular duals of planar triangular graphs, Proc. 3rd International Conference for Young Computer Scientists, Beijing, 1993, pp. 6.33-6.37. Complete version to appear in Algorithmica.

W. R. Heller, G. Sorkin and K. Mailing, The planar pachage planner for system designers, Proc. 19th IEEE Design Automation Conf., 1982, pp. 253-260.

G. Kant, Drawing planar graphs using the lmc-ordering, in Proc. 33th Ann. IEEE Symp. on Found. of Comp. Science, Pittsburgh, 1992, pp. 101-110.

G. Kant, A more compact visibility representation, in: J. van Leeuwen (Ed.), Proc. 19th Intern. Workshop on Graph-Theoretic Concepts in Comp. Science (WG '93).

G. Kant and X. He, Two algorithms for finding rectangular duals of planar graphs, in: J. van Leeuwen (Ed.), Proc. 19th Intern. Workshop on Graph-Theoretic Concepts in Comp. Science (WG '93), LNCS, Springer-Verlag, 1994, to appear.

K. Kózminski and E. Kinnen, Rectangular dual of planar graphs, Networks 15, 1985, pp. 145-157.

Y.-T. Lai and S. M. Leinwand, A theory of rectangular dual graphs, Algorithmica 5, 1990, pp. 467-483.

F. P. Preparata and R. Tamassia, Fully dynamic techniques for point location and transitive closure in planar structures, Proc. 29th FOCS, 1988, pp. 558-567.

R. C. Read, A new method for drawing a planar graph given the cyclic order of the edges at each vertex, Congressus Numerantium 56 (1987), pp. 31-44.

P. Rosenstiehl and R.E. Tarjan, Rectilinear planar layouts and bipolar orientations of planar graphs, Discr. and Comp. Geometry 1, 1986, pp. 343-353.

W. Schnyder, Embedding planar graphs on the grid, Abstracts of the Amer. Math. Soc., 9 (1988), p. 268.

W. Schnyder, Planar graphs and poset dimension, Orders 5 (1989), pp. 323-343.

W. Schnyder, Embedding planar graphs on the grid, in Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 138-148.

S. K. Stein, Convex maps, in Proc Amer Math Soc, vol.2, 1951, pp. 464-466.

R. Tamassia and J. S. Vitter, Parallel transitive closure and point location in planar structures, SIAM J. Comput. 20 (2), 1991, pp. 708-725.

R. Tamassia, Drawing Algorithms for Planar s-t Graphs, Australasian Journal of Combinatorics, Vol. 2, 1990, pp. 217-236.

R. Tamassia and I. Tollis, Tesselation Representations of Planar Graphs, in Proc. 27th Allerton Conference, 1989, pp. 48-57.

R. Tamassia and I. G. Tollis, A unified approach to visibility representations of planar graphs, Discr. and Comp. Geometry 1, 1986, pp. 321-341.#

R. Tamassia and I. G. Tollis, Planar grid embedding in linear time, IEEE Trans. Circuits and Systems 36, 1989, pp. 1230-1234.

W. Tutte, How to draw a graph, Proc. London Math. Soc. 13, 1963, pp.743-768.

K. Wagner, Bemerkungen zum Vierfarbenproblem, Jahresbericht Deutsch Math. Verein, 46 (1936), pp. 26-32.