creators_name: Fusy, Eric
editors_name: Kaufmann, Michael
editors_name: Wagner, Dorothea
editors_id: Kaufmann, Michael
editors_id: Wagner, Dorothea
type: confpaper
datestamp: 2007-05-04
lastmod: 2008-09-18 11:09:04
metadata_visibility: show
title: Straight-line drawing of quadrangulations
ispublished: pub
subjects: P.720
full_text_status: none
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.
    
date: 2007
date_type: published
series: Lecture notes in Computer Science
publisher: Springer
pagerange: 234-239
refereed: FALSE
referencetext: 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.
citation: Fusy, Eric (2007) Straight-line drawing of quadrangulations. [Conference Paper]