Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Tính Toán Cartograms Với Độ Phức Tạp Tối Ưu
Tóm tắt
Trong một đối xứng đường thẳng của một đồ thị phẳng, các đỉnh được biểu diễn bằng các đa giác đường thẳng đơn giản, trong khi các cạnh được biểu diễn bằng các tiếp xúc bên giữa các đa giác tương ứng. Một đối xứng đường thẳng được gọi là cartogram nếu diện tích của mỗi vùng bằng với một trọng số được chỉ định trước. Độ phức tạp của một cartogram được xác định bởi số góc (hoặc cạnh) tối đa cần thiết cho bất kỳ đa giác nào. Trong một loạt các bài báo, độ phức tạp đa giác của các biểu diễn này cho các đồ thị phẳng tối đa đã được giảm từ 40 ban đầu xuống 34, sau đó là 12 và gần đây nhất là 10, mức tốt nhất hiện nay. Ở đây, chúng tôi mô tả một cấu trúc với các đa giác 8 cạnh, tối ưu về độ phức tạp đa giác vì đôi khi đa giác 8 cạnh là cần thiết. Cụ thể, chúng tôi chỉ ra cách tính toán cấu trúc tổ hợp và cách tinh chỉnh nó thành một bố cục hình chữ nhật toàn diện theo diện tích trong thời gian tuyến tính. Cartogram chính xác có thể được tính từ bố cục toàn diện theo diện tích với phép lặp số học, hoặc có thể được xấp xỉ với một phương pháp leo đồi. Chúng tôi cũng mô tả một cấu trúc thay thế cho cartograms của các đồ thị phẳng tối đa Hamilton, cho phép chúng tôi tính toán trực tiếp các cartograms trong thời gian tuyến tính. Hơn nữa, chúng tôi chứng minh rằng ngay cả đối với các đồ thị Hamilton, đa giác đường thẳng 8 cạnh là cần thiết, bằng cách xây dựng một ví dụ có giới hạn dưới không tầm thường. Độ phức tạp của các cartograms có thể được giảm xuống 6 nếu đường đi Hamilton có thuộc tính bổ sung là một chân, như trong các đồ thị phẳng bên ngoài. Như vậy, chúng tôi có các biểu diễn tối ưu (về cả độ phức tạp đa giác và thời gian chạy) cho các đồ thị phẳng tối đa Hamilton và các đồ thị phẳng tối đa bên ngoài. Cuối cùng, chúng tôi đề cập đến vấn đề xây dựng cartograms có độ phức tạp nhỏ cho các đồ thị 4 kết nối (là Hamilton). Chúng tôi trước tiên bác bỏ một giả thuyết, do hai nhóm tác giả đưa ra, rằng bất kỳ đồ thị phẳng tối đa 4 kết nối nào cũng có một chu trình Hamilton một chân, từ đó vô hiệu hóa một nỗ lực đạt được độ phức tạp đa giác 6 trong cartograms cho lớp đồ thị này. Chúng tôi cũng chứng minh rằng việc quyết định liệu một đồ thị phẳng 4 kết nối nhất định có cho phép một cartogram tương ứng với hàm trọng số cho trước hay không là NP-khó.
Từ khóa
Tài liệu tham khảo
Alam, M.J., Kobourov, S.G.: Proportional contact representations of 4-connected planar graphs. In: Graph Drawing (GD’12), pp. 211–223. Springer (2013)
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’11), pp. 281–291. Springer, Berlin (2011)
Alam, M.J., Biedl, T.C., Felsner, S., Kaufmann, M., Kobourov, S.G.: Proportional contact representations of planar graphs. In: Graph Drawing (GD’11), pp. 26–38. Springer, Heidelberg (2012)
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’12), pp. 21–30. Bethesda (2012)
Biedl, T.C., Genc, B.: Complexity of octagonal and rectangular cartograms. In: Canadian Conference on, Computational Geometry (CCCG’05), pp. 117–120. Ontario (2005)
Biedl, T.C., Velázquez, L.E.R.: Orthogonal cartograms with few corners per face. In: Algorithms and Data Structures, Symposium (WADS’11), pp. 98–109. Springer, Berlin (2011)
Buchsbaum, A.L., Gansner, E.R., Procopiuc, C.M., Venkatasubramanian, S.: Rectangular layouts and contact graphs. ACM Trans. Algorithms 4, 28 (2008)
Cederbaum, I.: Analogy between VLSI floorplanning problems and realisation of a resistive network. IEE Circuits Devices Syst. 139(1), 99–103 (1992)
Chen, T., Fan, M.K.H.: On convex formulation of the floorplan area minimization problem. In: Symposium on Physical Design, pp. 124–128. (1998)
Chrobak, M., Payne, T.H.: A linear-time algorithm for drawing a planar graph on a grid. Inf. Process. Lett. 54(4), 241–246 (1995)
de Berg, M., Mumford, E., Speckmann, B.: On rectilinear duals for vertex-weighted plane graphs. Discrete Math. 309(7), 1794–1812 (2009)
de Berg, M., Mumford, E., Speckmann, B.: Optimal BSPs and rectilinear cartograms. Int. J. Comput. Geom. Appl. 20(2), 203–222 (2010)
de Fraysseix, H., Ossona de Mendez, P.: On triangle contact graphs. Comb. Probab. Comput. 3, 233–246 (1994)
de Fraysseix, H., Ossona de Mendez, P.: On topological aspects of orientations. Discrete Math. 229(1–3), 57–72 (2001)
de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)
Duncan, C.A., Gansner, E.R., Hu, Y.F., Kaufmann, M., Kobourov, S.G.: Optimal polygonal representation of planar graphs. Algorithmica 63(3), 672–691 (2012)
Eppstein, D., Mumford, E., Speckmann, B., Verbeek, K.: Area-universal and constrained rectangular layouts. SIAM J. Comput. 41(3), 537–564 (2012)
He, X.: On floor-plan of plane graphs. SIAM J. Comput. 28(6), 2150–2167 (1999)
Heilmann, R., Keim, D.A., Panse, C., Sips, M.: Recmap: Rectangular map approximations. In: IEEE Symposium on, Information Visualization (INFOVIS’04), pp. 33–40. Minneapolis (2004)
House, D., Kocmoud, C.: Continuous cartogram construction. In: Proceedings of IEEE Visualization, pp. 197–204. Triangle Park (1998)
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, 857–865 (1998)
Kawaguchi, A., Nagamochi, H.: Orthogonal drawings for plane graphs with specified face areas. In: Theory and Applications of Model of Computation (TAMC’07), pp. 584–594 . Springer, Berlin (2007)
Koebe, P.: Kontaktprobleme der konformen Abbildung. Berichte über die Verhandlungen der Sächsischen Akademie der Wissenschaften zu Leipzig. Math. Phys. Klasse 88, 141–164 (1936)
Koźmiński, K., Kinnen, E.: Rectangular duals of planar graphs. Networks 15, 145–157 (1985)
Leinwand, S.M., Lai, Y.T.: An algorithm for building rectangular floor-plans. In: Design Automation Conference, pp. 663–664. IEEE Press, Piscataway (1984)
Liao, C.C., Lu, H.I., Yen, H.C.: Compact floor-planning via orderly spanning trees. J. Algorithms 48, 441–451 (2003)
Michalek, J., Choudhary, R., Papalambros, P.: Architectural layout design optimization. Eng. Optim. 34(5), 461–484 (2002)
Moh, T.S., Chang, T.S., Hakimi, S.L.: Globally optimal floorplanning for a layout problem. IEEE Trans. Circuits Syst. 43(9), 713–720 (1996)
Nöllenburg, M., Prutkin, R., Rutter, I.: Edge-weighted contact representations of planar graphs. In: Graph Drawing (GD’12), pp. 224–235. Springer (2013)
Raisz, E.: The rectangular statistical cartogram. Geogr. Rev. 24(3), 292–296 (1934)
Rinsma, I.: Nonexistence of a certain rectangular floorplan with specified area and adjacency. Environ. Plan. 14, 163–166 (1987)
Rosenberg, E.: Optimal module sizing in VLSI floorplanning by nonlinear programming. Methods Models Oper. Res. 33, 131–143 (1989)
Schnyder, W.: Embedding planar graphs on the grid. In: Symposium on Discrete Algorithms (SODA’90), pp. 138–148. San Francisco (1990)
Tobler, W.: Thirty five years of computer cartograms. Ann. Assoc. Am. Geogr. 94, 58–73 (2004)
Ueckerdt, T.: Geometric representations of graphs with low polygonal complexity. Ph.D. Thesis, Technische Universität, Berlin (2011)
Ungar, P.: On diagrams representing maps. J. Lond. Math. Soc. 28, 336–342 (1953)
van Kreveld, M.J., Speckmann, B.: On rectangular cartograms. Comput. Geom. 37(3), 175–187 (2007)
Wang, K., Chen, W.K.: Floorplan area optimization using network analogous approach. In: IEEE Transactions Circuits and Systems, pp. 167–170 (1995)
Wimer, S., Koren, I., Cederbaum, I.: Floorplans, planar graphs, and layouts. IEEE Trans. Circuits Syst. 35(3), 267–278 (1988)
Yeap, K.H., Sarrafzadeh, M.: Floor-planning by graph dualization: 2-concave rectilinear modules. SIAM J. Comput. 22, 500–526 (1993)