Logo

Login

Upward Planarity Checking: "Faces Are More than Polygons" (Extended Abstract)

Di Battista, Giuseppe and Liotta, Giuseppe (1998) Upward Planarity Checking: "Faces Are More than Polygons" (Extended Abstract). [Conference Paper]

Full text not available from this repository.

Abstract

In this paper we look at upward planarity from a new perspective. Namely, we study the problem of checking whether a given drawing is upward planar. Our checker exploits the relationships between topology and geometry of upward planar drawings to verify the upward planarity of a significant family of drawings. The checker is simple and optimal both in terms of efficiency and in terms of degree.

Item Type:Conference Paper
Classifications:P Styles > P.840 Upward
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.540 Planar
ID Code:244
Deposited By:Arnopolina, Galina
Deposited On:09 Nov 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=1547&spage=72

Repository Staff Only: item control page

References

1. P. Bertolazzi, G. Di Battista, and W. Didimo. Quasi upward planarity. Manuscript, 1998.

2. P. Bertolazzi, G. Di Battista, G. Liotta, and C. Mannino. Upward drawings for triconnected digraphs. Algoritmica, 6(12):476-497, 1994.

3. B. Chazelle. Triangulating a simple polygon in linear time. Discrete Comput. Geom., 6:485-524, 1991.

4. B. Chazelle and J. Incepri. Triangulation and shape-complexity. ACM Trans. Graph., 3(2):135-152, 1984.

5. O. Devillers, G. Liotta, R. Tamassia, and F. Preparata. Checking the convexity of polytopes and the planarity of subdivisions. In Algorithms and Data Structures (Proc. WADS 97), vol. 1272 of LNCS, pages 186-199, Springer-Verlag, 1997.

6. G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4:235-282, 1994.

7. G. Di Battista and R. Tamassia. Algorithms for plane representations of acyclic digraphs. Theoret. Comput. Sci., 61:175-198, 1988.

8. H. ElGindy, D. Avis, and G. T. Toussaint. Applications of a two-dimensionalhidden-line algorithm to other geometirc problem. Computing, 31:191-202, 1983.

9. K.R. Gabriel and R.R. Sokal. A new statistical approach to geographical analysis. Systematic Zoology. 18:54-64, 1969.

10. M.R. Garey, D.S. Johnson, F.P. Preparata, and R.E. Tarjan. Triangulating a simple polygon. Inform. Process. Lett., 7:175-179, 1978.

11. F. Harary. Graph Theory. Addison-Wesley, Reading, MA, 1972.

12. S. Hertel and K. Mehlhorn. Fast triangulation of simple polygons. In Proc. 4th Internat. Conference Found. Comp. Theory, vol. 158 of LNCS, pages 207-218, Springer-Verlag, 1983.

13. D. Kelly. Fundamentals of planar ordered sets. Discrete Math., 63:197-216, 1987.

14. G. Liotta, F.P. Preparata, and R. Tamassia. Robust proximity queries: an illustration of degree-driven algorithm design. SIAM J. Comput. to appear.

15. G. Liotta, F.P. Preparata, and R. Tamassia. Robust proximity queries: an illustration of degree-driven algorithm design. In proc. 13th Annu. ACM Symp. Comput. Geom., pages 156-165,1997.

16. K. Mehlhorn and S. Näher. Checkin Geometric Structures, Dec. 1996. Manual.

17. K. Mehlhorn, S. Näher, T. Schilz, S. Schirra, M. Seel, R. Seidel, and C. Uhrig. Checkin geometric programs or verification of geometric structures. In Proc. 12th Annu. ACM Symp. Comp. Geom., pages 159-165, 1996.

18. K. Mehlhorn, S. Näher, T. Schilz, S. Schirra, M. Seel, R. Seidel, and C. Uhrig. Checkin geometric programs or verification of geometric structures. Manuscript, 1997.

19. Franco P. Preparata and Michael I. Shamos. Computational geometry: an introduction. Springer-Verlag, New-York, 1985.

20. G. Toussaint. Efficient triangulation of simple polygons. Visual Comput., 7:280-295, 1991.

21. G. Toussaint. The relative neighborhood graph of a finite planar set. Pattern Recognition, 12:261-268, 1980.

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.