On Drawing a Graph Convexly in the Plane (Extended Abstract)

Djidjev, Hristo (1995) On Drawing a Graph Convexly in the Plane (Extended Abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 76-83 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_358).

Full text not available from this repository.


Let G be a planar graph and H be a subgraph of G. Given any convex drawing of H, we investigate the problem of how to extend the drawing of H to a convex drawing of G. We obtain a necessary and sufficient condition for the existence and a linear algorithm for the construction of such an extension. Our results and their corollaries generalize previous theoretical and algorithmic results of Tutte, Thomassen, Chiba, Yamanouchi, and Nishizeki.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_358
Classifications:M Methods > M.999 Others
Z Theory > Z.250 Geometry
G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
P Styles > P.540 Planar
ID Code:100

Repository Staff Only: item control page


G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis, Algorithms for drawing graphs: an annotated Bibliography, Technical Report, Brown University, 1988; updated 1993.

Guiseppe Di Battista, Roberto Tamassia, and Luca Vismara, On-line convex planarity testing, Proc. WG'94, in Lecture Notes in Computer Science, Springer-Verlag, to appear.

K. Booth, G. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithm, J. Comp. Sci. 13, 1976, pp. 335-379.

N. Chiba, T. Nishizeki, S. Abe, T. Ozawa, A linear algorithm for embedding planar graphs using PQ-trees, J. Comput. System Sci. 30, 1985, 54-76.

N. Chiba, T. Yamanouchi, T. Nishizeki, Linear algorithms for convex drawings of planar graphs, in Progress in Graph Theory, J.A. Bondy and U.S.R. Murty (eds.), Academic Press, 1984, pp. 153-173.

M. Chrobak and G. Kant, Convex grid drawings of 3-connected planar graphs, Technical Report RUU-CS-93-45, Utrecht University, 1993.

S. Even and R.E. Tarjan, Computing an st-numbering, Theor. Comput. Sci. 2, 1976, 339-344.

J. Hopcroft and R.E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput. 2, 1973, pp. 135-158.

J. Hopcroft and R.E. Tarjan Efficient planarity testing, J. ACM, 21:4, 1974, pp. 549-568.

G. Kant, Drawing planar graphs using the lmc-ordering, Proc. IEEE Symp. on Foundations of Computer Science, 1992, pp. 101-110.

A. Lempel, S. Even, I. Cederbaum, An algorithm for planarity testing of a graph, Theory of Graphs: International Symposium, Gordon and Breach, New York, 1967, pp. 215-232.

T. Nishizeki, N. Chiba, Planar Graphs: Theory and Algorithms, North Holland, 1988.

W. Schnyder and W. Trotter, Convex drawings of planar graphs, Abstracts of the AMS, vol. 13, 1992.

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

C. Thomassen, Planarity and duality of finite and infinite planar graphs, J. Combinatorial Theory, Series B 29, 1980, pp. 244-271.

W.T. Tutte, Convex representations of graphs, Proc. London Math Soc., vol. 10, 1960, pp. 304-320.

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

K. Wagner, Bemerkungen zum Vierfarbenproblem, Jber. Deutsch. Math.-Verein, vol. 46, 1936, pp. 26-32.