Abstract
We use Schnyder woods of 3-connected planar graphs to produce convex straight line drawings on a grid of size (n − 2 − Δ) ×(n − 2 − Δ). The parameter Δ≥ 0 depends on the the Schnyder wood used for the drawing. This parameter is in the range \(0 \leq \Delta\leq \frac{n}{2}-2\).
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Rote, G.: Strictly convex drawings of planar graphs (2004)
Rosenstiehl, P., Tarjan, R.E.: Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom. 1, 343–353 (1986)
Schnyder, W.: Planar graphs and poset dimension. Order 5, 323–343 (1989)
de Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting Fary embeddings of planar graphs. In: Proc. 20th Annu. ACM Sympos. Theory Comput., pp. 426–433 (1988)
de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10, 41–51 (1990)
He, X.: Grid embeddings of 4-connected plane graphs. Discrete Comput. Geom. 17, 339–358 (1997)
Miura, K., Nakano, S., Nishizeki, T.: Grid drawings of 4-connected plane graphs. Discrete Comput. Geom. 26, 73–87 (2001)
Schnyder, W.: Embedding planar graphs on the grid. In: Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pp. 138–148 (1990)
Zhang, H., He, X.: Compact visibility representation and straight-line grid embedding of plane graphs. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 493–504. Springer, Heidelberg (2003)
Tutte, W.T.: Convex representations of graphs. Proceedings London Mathematical Society 10, 304–320 (1960)
Tutte, W.T.: How to draw a graph. Proceedings London Mathematical Society 13, 743–768 (1963)
Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16, 4–32 (1996)
Chrobak, M., Kant, G.: Convex grid drawings of 3-connected planar graphs. Internat. J. Comput. Geom. Appl. 7, 211–223 (1997)
Schnyder, W., Trotter, W.T.: Convex embeddings of 3-connected plane graphs. Abstracts of the AMS 13, 502 (1992)
Di Battista, G., Tamassia, R., Vismara, L.: Output-sensitive reporting of disjoint paths. Algorithmica 23, 302–340 (1999)
Felsner, S.: Convex drawings of planar graphs and the order dimension of 3-polytopes. Order, 19–37 (2001)
Felsner, S.: Geometric Graphs and Arrangements. Vieweg Verlag (2004)
Felsner, S.: Lattice structures from planar graphs. Electron. J. Comb. 11 R15, 24p. (2004)
Fusy, E., Poulalhon, D., Schaeffer, G.: Coding, counting and sampling 3-connected planar graphs. In: 16th ACM-SIAM Sympos. Discrete Algorithms (2005) (to appear)
Bonichon, N., Gavoille, C., Hanusse, N., Poulalhon, D., Schaeffer, G.: Planar graphs, via well-orderly maps and trees. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 270–284. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bonichon, N., Felsner, S., Mosbah, M. (2005). Convex Drawings of 3-Connected Plane Graphs. In: Pach, J. (eds) Graph Drawing. GD 2004. Lecture Notes in Computer Science, vol 3383. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31843-9_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-31843-9_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24528-5
Online ISBN: 978-3-540-31843-9
eBook Packages: Computer ScienceComputer Science (R0)