Straight-line drawing of quadrangulations

Fusy, Eric (2007) Straight-line drawing of quadrangulations. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 234-239 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_23).

Full text not available from this repository.

Abstract

This article introduces a straight-line drawing algorithm for quadrangulations, in the family of the face-counting algorithms. It outputs in linear time a drawing on a regular W x H grid such that W+H=n-1-Delta, where n is the number of vertices and Delta is an explicit combinatorial parameter of the quadrangulation.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_23
Classifications:P Styles > P.720 Straight-line
ID Code:778

Repository Staff Only: item control page

References

Therese Biedl and Franz J. Brandenburg. Drawing planar bipartite graphs with small area. In Proceedings of CCCG, Windsor, pages 105-108, 2005.

N. Bonichon, S. Felsner, and M. Mosbah. Convex drawings of 3-connected plane graphs. In Proceedings of Graph Drawing, pages 287-299. Springer-Verlag, 2004.

H. de Fraysseix, P. Ossona de Mendez, and J. Pach. A left-first search algorithm for planar graphs. Discrete Comput. Geom., 13:459-468, 1995.

H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Bipolar orientations revisited. Discrete Appl. Math., 56(2-3):157-179, 1995.

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

E. Fusy. Transversal structures on triangulations, with application to straight-line drawing. In Proceedings of Graph Drawing, LNCS 3843, pages pp. 177-188, 2005. Full paper with proofs available at http://arxiv.org/abs/math.CO/0602163.

C. Huemer and S. Kappes. A binary labelling for plane laman graphs and quadrangulations. In Proceedings of EWCG, Delphi, pages 83-86, 2006.

G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16(1):4-32, 1996.

G. Kant and Xin He. Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoretical Computer Science, 172(1-2):175-193, 1997.

K. Miura, S. Nakano, and T. Nishizeki. Grid drawings of four-connected plane graphs. Disc. Comput. Geometry, 26(2):73-87, 2001.

W. Schnyder. Embedding planar graphs on the grid. In Proceedings of the first annual ACM-SIAM Symposium on Discrete Algorithms, pages 138-148, 1990.