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)

Postscript - Requires a viewer, such as GSview


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


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.