Abstract
In this paper, we consider the problem of representing planar graphs by polygons whose sides touch. We show that at least six sides per polygon are necessary by constructing a class of planar graphs that cannot be represented by pentagons. We also show that the lower bound of six sides is matched by an upper bound of six sides with a linear-time algorithm for representing any planar graph by touching hexagons. Moreover, our algorithm produces convex polygons with edges having at most three slopes and with all vertices lying on an O(n)×O(n) grid.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alam, M.J., Biedl, T., Felsner, S., Kaufmann, M., Kobourov, S.G.: Proportional contact representations of planar graphs. Tech. Rep. CS 2011-11, 2011, http://www.cs.uwaterloo.ca/research/tr/2011/CS-2011-11.pdf
Battista, G.D., Lenhart, W., Liotta, G.: Proximity drawability: a survey. In: Graph Drawing. Lecture Notes in Computer Science, vol. 894, pp. 328–39. Springer, Berlin (1994)
de Berg, M., Mumford, E., Speckmann, B.: On rectilinear duals for vertex-weighted plane graphs. Discrete Math. 309(7), 1794–1812 (2009)
Biedl, T., Bretscher, A., Meijer, H.: Rectangle of influence drawings of graphs without filled 3-cycles. In: Graph Drawing. Lecture Notes in Computer Science, vol. 1731, pp. 359–368. Springer, Berlin (1999)
Bruls, M., Huizing, K., van Wijk, J.J.: Squarified treemaps. In: Proceedings of the Joint Eurographics/IEEE TVCG Symposium on Visualization, VisSym, pp. 33–42 (2000)
Buchsbaum, A.L., Gansner, E.R., Procopiuc, C.M., Venkatasubramanian, S.: Rectangular layouts and contact graphs. ACM Trans. Algorithms 4(1), 8:1–8:28 (2008)
Chrobak, M., Payne, T.: A linear-time algorithm for drawing planar graphs. Inf. Process. Lett. 54, 241–246 (1995)
Duncan, C.A., Gansner, E.R., Hu, Y.F., Kaufmann, M., Kobourov, S.G.: Optimal polygonal representation of planar graphs. ArXiv e-prints, Apr. 2011, arXiv:1104.1482
de Fraysseix, H., de Mendez, P.O., Rosenstiehl, P.: On triangle contact graphs. Comb. Probab. Comput. 3, 233–246 (1994)
de Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting Fary embeddings of planar graphs. In: Proceedings of the 20th Symposium on the Theory of Computing (STOC), pp. 426–433 (1988)
de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)
Gabriel, K.R., Sokal, R.R.: A new statistical approach to geographical analysis. Syst. Zool. 18, 54–64 (1969)
Gansner, E.R., Hu, Y., Kobourov, S.: On touching triangle graphs. In: Graph Drawing. Lecture Notes in Computer Science, vol. 6502, pp. 250–261. Springer, Berlin (2011), http://dx.doi.org/10.1007/978-3-642-18469-7_23
Gonçalves, D., Lévêque, B., Pinlou, A.: Triangle contact representations and duality. In: Graph Drawing. Lecture Notes in Computer Science, vol. 6502, pp. 262–273. Springer, Berlin (2011). http://dx.doi.org/10.1007/978-3-642-18469-7_24
He, X.: On finding the rectangular duals of planar triangular graphs. SIAM J. Comput. 22(6), 1218–1226 (1993)
He, X.: On floor-plan of plane graphs. SIAM J. Comput. 28(6), 2150–2167 (1999)
Hliněný, P.: Classes and recognition of curve contact graphs. J. Comb. Theory, Ser. B 74(1), 87–103 (1998)
Hliněný, P., Kratochvíl, J.: Representing graphs by disks and balls (a survey of recognition-complexity results). Discrete Math. 229(1–3), 101–124 (2001)
Hopcroft, J., Tarjan, R.E.: Efficient planarity testing. J. ACM 21(4), 549–568 (1974)
Jaromczyk, J.W., Toussaint, G.T.: Relative neighborhood graphs and their relatives. Proc. IEEE 80, 1502–1517 (1992)
Kant, G.: Hexagonal grid drawings. In: 18th Workshop on Graph-Theoretic Concepts in Computer Science, pp. 263–276 (1992)
Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16, 4–32 (1996) (special issue on Graph Drawing, edited by G. Di Battista and R. Tamassia)
Kant, G., He, X.: Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theor. Comput. Sci. 172, 175–193 (1997)
Koebe, P.: Kontaktprobleme der konformen Abbildung. Ber. Verh. K. Sächs. Ges. Wiss. Leipz., Math.-Phys. Kl. 88, 141–164 (1936)
Koźmiński, K., Kinnen, W.: Rectangular dualization and rectangular dissections. IEEE Trans. Circuits Syst. 35(11), 1401–1416 (1988)
Lai, Y.-T., Leinwand, S.M.: Algorithms for floorplan design via rectangular dualization. IEEE Trans. Comput.-Aided Des. 7, 1278–1289 (1988)
Lai, Y.-T., Leinwand, S.M.: A theory of rectangular dual graphs. Algorithmica 5, 467–483 (1990)
Liao, C.-C., Lu, H.-I., Yen, H.-C.: Compact floor-planning via orderly spanning trees. J. Algorithms 48, 441–451 (2003)
Liotta, G., Lubiw, A., Meijer, H., Whitesides, S.H.: The rectangle of influence drawability problem. Comput. Geom. Theory Appl. 10, 1–22 (1998)
Rahman, M., Nishizeki, T., Ghosh, S.: Rectangular drawings of planar graphs. J. Algorithms 50(1), 62–78 (2004)
Steadman, P.: Graph-theoretic representation of architectural arrangement. In: The Architecture of Form, pp. 94–115. Cambridge University Press, Cambridge (1976)
Thomassen, C.: Plane representations of graphs. In: Progress in Graph Theory, pp. 43–69 (1982)
Thomassen, C.: Interval representations of planar graphs. J. Comb. Theory, Ser. B 40, 9–20 (1988)
Walker, J.Q., II: A node-positioning algorithm for general trees. Softw. Pract. Exp. 20(7), 685–705 (1990)
Yeap, G.K., Sarrafzadeh, M.: Sliceable floorplanning by graph dualization. SIAM J. Discrete Math. 8(2), 258–280 (1995)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper appeared in LATIN 2010, Oaxaca, Mexico.
Rights and permissions
About this article
Cite this article
Duncan, C.A., Gansner, E.R., Hu, Y.F. et al. Optimal Polygonal Representation of Planar Graphs. Algorithmica 63, 672–691 (2012). https://doi.org/10.1007/s00453-011-9525-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-011-9525-2