Drawing Planar Bipartite Graphs With Small Area

Biedl, Therese and Brandenburg, Franz J. (2005) Drawing Planar Bipartite Graphs With Small Area. In: Canadian Conference on Computational Geometry, August 10-12, 2005, Windsor, Ontario, Canada , pp. 105-108 . (In Press)

[img]
Preview
 Postscript - Requires a viewer, such as GSview
132Kb

Abstract

In this paper, we study planar straight-line drawings of bipartite planar graphs. We show that these graphs admit drawings in an n/2 x (n/2-1) -grid, and that this is optimal. Our results generalize to triangle-free planar graphs.

Item Type:Conference Paper
Keywords:bipartite planar graphs
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
ID Code:604

Repository Staff Only: item control page

References

T. Biedl and F. Brandenburg. Partitions of graphs into trees, 2005. In preparation.

T. Biedl, G. Kant, and M. Kaufmann. On triangulating planar graphs under the four-connectivity constraint. Algorithmica, 19(4):427--446, 1997.

T. Biedl, M. Kaufmann, and P. Mutzel. Drawing planar partitions II: HH-drawings. In Workshop on Graph-Theoretic Concepts in Computer Science, volume 1517 of Lecture Notes in Computer Science, pages 124--136. Springer-Verlag, 1998.

F. Brandenburg, D. Eppstein, M.T. Goodrich, S.G. Kobourov, G. Liotta, and P. Mutzel. Selected open problems in graph drawing. In Graph Drawing, volume 2912 of Lecture Notes in Computer Science, pages 320--331. Springer-Verlag, 2003.

M. Chrobak and S. Nakano. Minimum-width grid drawings of plane graphs. Computational Geometry: Theory and Applications, 11(1):29--54, 1998.

I. Fáry. On straight line representation of planar graphs. Acta. Sci. Math. Szeged, 11:229--233, 1948.

U. Fößmeier and M. Kaufmann. Nice drawings for planar bipartite graphs. In 3rd Italian Conference on Algorithms and Complexity, CIAC '97, volume 1203 of Lecture Notes in Computer Science, pages 122--134. Springer-Verlag, 1997.

H. de Fraysseix, J. Pach, and R. Pollack. Small sets supporting fary embeddings of planar graphs. In: Twentieth Annual ACM Symposium on Theory of Computing, pages 426--433, 1988.

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

G. Kant and X. He. Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoret. Comput. Sci., 172(1-2):175--193, 1997.

K. Miura, T. Nishizeki, and S. Nakano. Grid drawings of 4-connected plane graphs. Discrete Computational Geometry, 26:73--87, 2001.

W. Schnyder. Embedding planar graphs on the grid. In 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 138--148, 1990.

S. Stein. Convex maps. In Amer. Math. Soc., volume 2, pages 464--466, 1951.

K. Wagner. Bemerkungen zum Vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung, 46:26--32, 1936.

H. Zhang and X. He. Compact visibility representations and straight-line grid embedding of plane graphs. In Workshop on Algorithms and Data Structures (WADS'03), volume 2748 of Lecture Notes in Computer Science, pages 493--504. Springer-Verlag, 2003.