Linear-Time Algorithms for Hole-free Rectilinear Proportional Contact Graph Representations

详细信息    查看全文

• 作者：M. Jawaherul Alam (1)
  Therese Biedl (2)
  Stefan Felsner (3)
  Andreas Gerasch (4)
  Michael Kaufmann (4)
  Stephen G. Kobourov (1)
  
• 关键词：Graph drawing ; Contact representation ; Cartogram ; Planar graph ; Polygon
• 刊名：Algorithmica
• 出版年：2013
• 出版时间：September 2013
• 年：2013
• 卷：67
• 期：1
• 页码：3-22
• 全文大小：763KB
• 参考文献：1. Alam, M.J., Biedl, T.C., Felsner, S., Gerasch, A., Kaufmann, M., Kobourov, S.G.: Linear-time algorithms for hole-free rectilinear proportional contact graph representations. In: International Symposium on Algorithms and Computation (ISAAC鈥?1). Lecture Notes in Computer Science, vol. 7074, pp. 281鈥?91. Springer, Berlin (2011) CrossRef
  2. Alam, M.J., Biedl, T.C., Felsner, S., Kaufmann, M., Kobourov, S.G., Ueckerdt, T.: Computing cartograms with optimal complexity. In: Symposium on Computational Geometry (SoCG鈥?2), pp. 21鈥?0. ACM, New York (2012)
  3. de Berg, M., Mumford, E., Speckmann, B.: On rectilinear duals for vertex-weighted plane graphs. Discrete Math. 309(7), 1794鈥?812 (2009) CrossRef
  4. Biedl, T.C., Vel谩zquez, L.E.R.: Orthogonal cartograms with few corners per face. In: Workshop on Algorithms and Data Structures (WADS鈥?1). Lecture Notes in Computer Science, vol. 6844, pp. 98鈥?09. Springer, Berlin (2011) CrossRef
  5. Biedl, T.C., Vel谩zquez, L.E.R.: Drawing planar 3-trees with given face areas. Comput. Geom. 46(3), 276鈥?85 (2013) CrossRef
  6. Buchsbaum, A.L., Gansner, E.R., Procopiuc, C.M., Venkatasubramanian, S.: Rectangular layouts and contact graphs. ACM Trans. Algorithms 4(1), 8 (2008). doi:10.1145/1328911.1328919 CrossRef
  7. Duncan, C.A., Gansner, E.R., Hu, Y.F., Kaufmann, M., Kobourov, S.G.: Optimal polygonal representation of planar graphs. Algorithmica 63(3), 672鈥?91 (2012) CrossRef
  8. de Fraysseix, H., de Mendez, P.O.: On topological aspects of orientations. Discrete Math. 229(1鈥?), 57鈥?2 (2001) CrossRef
  9. de Fraysseix, H., de Mendez, P.O., Rosenstiehl, P.: On triangle contact graphs. Comb. Probab. Comput. 3, 233鈥?46 (1994) CrossRef
  10. He, X.: On floor-plan of plane graphs. SIAM J. Comput. 28(6), 2150鈥?167 (1999) CrossRef
  11. Heilmann, R., Keim, D.A., Panse, C., Sips, M.: Recmap: Rectangular map approximations. In: IEEE Symposium on Information Visualization (INFOVIS鈥?4), pp. 33鈥?0 (2004) CrossRef
  12. Izumi, T., Takahashi, A., Kajitani, Y.: Air-pressure model and fast algorithms for zero-wasted-area layout of general floorplan. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E81-A(5), 857鈥?65 (1998). Special section on discrete mathematics and its applications
  13. Kant, G.: A more compact visibility representation. Int. J. Comput. Geom. Appl. 7(3), 197鈥?10 (1997) CrossRef
  14. Kawaguchi, A., Nagamochi, H.: Orthogonal drawings for plane graphs with specified face areas. In: Theory and Applications of Models of Computation (TAMC鈥?7). Lecture Notes in Computer Science, vol. 4484, pp. 584鈥?94. Springer, Berlin (2007) CrossRef
  15. Koebe, P.: Kontaktprobleme der konformen Abbildung. Berichte 眉ber die Verhandlungen der S盲chsischen Akademie der Wissenschaften zu Leipzig. Math.-Phys. Klasse 88, 141鈥?64 (1936)
  16. Ko藕mi艅ski, K., Kinnen, E.: Rectangular duals of planar graphs. Networks 15, 145鈥?57 (1985) CrossRef
  17. van Kreveld, M.J., Speckmann, B.: On rectangular cartograms. Comput. Geom. 37(3), 175鈥?87 (2007) CrossRef
  18. Liao, C.C., Lu, H.I., Yen, H.C.: Compact floor-planning via orderly spanning trees. J.聽Algorithms 48(2), 441鈥?51 (2003) CrossRef
  19. Mondal, D., Nishat, R.I., Rahman, M.S., Alam, M.J.: Minimum-area drawings of plane 3-trees. J.聽Graph Algorithms Appl. 15(2), 177鈥?04 (2011) CrossRef
  20. Rahman, M.S., Miura, K., Nishizeki, T.: Octagonal drawings of plane graphs with prescribed face areas. Comput. Geom. 42(3), 214鈥?30 (2009) CrossRef
  21. Ringel, G.: Equiareal graphs. In: Bodendiek, R. (ed.) Contemporary Methods in Graph Theory, pp.聽503鈥?05. Wissenschaftsverlag, Berlin (1990)
  22. Rinsma, I.: Nonexistence of a certain rectangular floorplan with specified area and adjacency. Environ. Plan. B, Plan. Des. 14, 163鈥?66 (1987) CrossRef
  23. Schnyder, W.: Embedding planar graphs on the grid. In: Symposium on Discrete Algorithms (SODA鈥?0), pp. 138鈥?48 (1990)
  24. Sun, Y., Sarrafzadeh, M.: Floorplanning by graph dualization: / L-shaped modules. Algorithmica 10(6), 429鈥?56 (1993) CrossRef
  25. Thomassen, C.: Plane cubic graphs with prescribed face areas. Comb. Probab. Comput. 1, 371鈥?81 (1992) CrossRef
  26. Ungar, P.: On diagrams representing graphs. J.聽Lond. Math. Soc. 28, 336鈥?42 (1953) CrossRef
  27. Wang, K., Chen, W.K.: Floorplan area optimization using network analogous approach. In: IEEE International Symposium on Circuits and Systems, vol. 1, pp. 167鈥?70 (1995)
  28. Yeap, K.H., Sarrafzadeh, M.: Floor-planning by graph dualization: 2-concave rectilinear modules. SIAM J. Comput. 22, 500鈥?26 (1993) CrossRef
  
• 作者单位：M. Jawaherul Alam (1)
  Therese Biedl (2)
  Stefan Felsner (3)
  Andreas Gerasch (4)
  Michael Kaufmann (4)
  Stephen G. Kobourov (1)
  
  1. Department of Computer Science, University of Arizona, Tucson, AZ, USA
  2. David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada
  3. Institut f眉r Mathematik, Technische Universit盲t Berlin, Berlin, Germany
  4. Wilhelm-Schickhard-Institut f眉r Informatik, T眉bingen Universit盲t, T眉bingen, Germany
  

文摘

In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. In this paper we first study proportional contact representations that use rectilinear polygons without wasted areas (white space). In this setting, the best known algorithm for proportional contact representation of a maximal planar graph uses 12-sided rectilinear polygons and takes O(nlogn) time. We describe a new algorithm that guarantees 10-sided rectilinear polygons and runs in O(n) time. We also describe a linear-time algorithm for proportional contact representation of planar 3-trees with 8-sided rectilinear polygons and show that this is optimal, as there exist planar 3-trees that require 8-sided polygons. We then show that a maximal outer-planar graph admits a proportional contact representation using rectilinear polygons with 6 sides when the outer-boundary is a rectangle and with 4 sides otherwise. Finally we study maximal series-parallel graphs. Here we show that O(1)-sided rectilinear polygons are not possible unless we allow holes, but 6-sided polygons can be achieved with arbitrarily small holes.