Logo

Login | Create Account

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). [Conference Paper]

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
Classifications:A General Literature > A.001 Introductory and Survey
ID Code:573
Deposited By:Selbach, Anna
Deposited On:23 Aug 2005
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=3383&spage=60

Repository Staff Only: item control page

References

1. Rote, G.: Strictly convex drawings of planar graphs (2004)

2. Rosenstiehl, P., Tarjan, R.E.: Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom. 1 (1986) 343-353

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

4. 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

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

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

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

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

9. 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

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

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

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

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

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

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

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

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

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

19. Fusy, E., Poulalhon, D., G. Schaeffer: Coding, counting and sampling 3-connected planar graphs. In: 16th ACM-SIAM Sympos. Discrete Algorithms. (2005) to appear.

20. 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)

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.