Convex Drawings of 3-Connected Plane Graphs (Extended Abstract)

Bonichon, Nicolas and Felsner, Stefan and Mosbah, Mohamed (2004) Convex Drawings of 3-Connected Plane Graphs (Extended Abstract). In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 60-70 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_8).

Full text not available from this repository.

Abstract

We use Schnyder woods of 3-connected planar graphs to produce convex straight line drawings on a grid of size (n-2-\Delta) x (n-2-\Delta). The parameter \Delta >= 0 depends on the the Schnyder wood used for the drawing. This parameter is in the range 0 <= \Delta <= \frac{n}{2} - 2.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_8
Classifications:A General Literature > A.001 Introductory and Survey
ID Code:573

Repository Staff Only: item control page

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 (1986) 343-353

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

de Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting Fary embeddings of planar graphs. In: Proc. 20th Annu. ACM Sympos. Theory Comput. (1988) 426-433

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

He, X.: Grid embeddings of 4 connected plane graphs. Discrete Comput. Geom. 17 (1997) 339-358

Miura, K., Nakano, S., Nishizeki, T.: Grid drawings of 4-connected plane graphs. Discrete Comput. Geom. 26 (2001) 73-87

Schnyder, W.: Embedding planar graphs on the grid. In: Proc. 1st ACM-SIAM Sympos. Discrete Algorithms. (1990) 138-148

Zhang, H., He, X.: Compact visibility representation and straight-line grid embedding of plane graphs. In: Proceedings WADS '93. Volume 2748 of Lecture Notes in Computer Science, Springer-Verlag (2003) 493-504

Tutte, W.T.: Convex representations of graphs. Proceedings London Mathematical Society 10 (1960) 304-320

Tutte, W.T.: How to draw a graph. Proceedings London Mathematical Society 13 (1963) 743-768

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

Chrobak, M., Kant, G.: Convex grid drawings of 3-connected plane graphs. Internat. J. Comput. Geom. Appl. 7 (1997) 211-223

Schnyder, W., Trotter, W.T.: Convex embeddings of 3-connected plane graphs. Abstracts of the AMS 13 (1992) 502

Di Battista, G., Tamassia, R., Vismara, L.: Output-sensitive reporting of disjoint paths. Algorithmica 23 (1999) 302-340

Felsner, S.: Convex drawings of planar graphs and the order dimension of 3-polytopes. Order (2001) 19-37

Felsner, S.: Geometric Graphs and Arrangements. Vieweg Verlag (2004)

Felsner, S.: Lattice structures from planar graphs. Electron. J. Comb. 11 R15 (2004) 24p.

Fusy, E., Poulalhon, D., G. Schaeffer: 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: Proceedings WG '04. Lecture Notes in Comput. Sci., Springer-Verlag (2004)