Proportional Contact Representations of 4-Connected Planar Graphs

Alam, Muhammed Jawaherul and Kobourov, Stephen G. (2013) Proportional Contact Representations of 4-Connected Planar Graphs. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 211-223 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_19).

Full text not available from this repository.

Abstract

In a contact representation of a planar graph, vertices are represented by interior-disjoint polygons and two polygons share a non-empty common boundary when the corresponding vertices are adjacent. In the weighted version, a weight is assigned to each vertex and a contact representation is called proportional if each polygon realizes an area proportional to the vertex weight. In this paper we study proportional contact representations of 4-connected internally triangulated planar graphs. The best known lower and upper bounds on the polygonal complexity for such graphs are 4 and 8, respectively. We narrow the gap between them by proving the existence of a representation with complexity 6. We then disprove a 10-year old conjecture on the existence of a Hamiltonian canonical cycle in a 4-connected maximal planar graph, which also implies that a previously suggested method for constructing proportional contact representations of complexity 6 for these graphs will not work. Finally we prove that it is NP-hard to decide whether a 4-connected planar graph admits a proportional contact representation using only rectangles.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_19
Classifications:P Styles > P.999 Others
Z Theory > Z.500 Representations
ID Code:1311

Repository Staff Only: item control page

References

Alam, M.J., Biedl, T., Felsner, S., Kaufmann, M., Kobourov, S.G.: Proportional Contact Representations of Planar Graphs. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, 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 2012, pp. 21–30 (2012)

Buchsbaum, A.L., Gansner, E.R., Procopiuc, C.M., Venkatasubramanian, S.: Rectangular layouts and contact graphs. ACM Transactions on Algorithms 4(1) (2008)

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 Journal on Computing 41(3), 537–564 (2012)

Felsner, S., Francis, M.C.: Contact representations of planar graphs with cubes. In: Symposium on Computational Geometry, SoCG 2011, pp. 315–320 (2011)

de Fraysseix, H., de Mendez, P.O., Rosenstiehl, P.: On triangle contact graphs. Combinatorics, Probability and Computing 3, 233–246 (1994)

de Fraysseix, H., de Mendez, P.O.: On topological aspects of orientations. Discrete Mathematics 229(1-3), 57–72 (2001)

Fusy, É.: Transversal structures on triangulations: A combinatorial study and straight-line drawings. Discrete Mathematics 309(7), 1870–1894 (2009)

He, X.: On floor-plan of plane graphs. SIAM Journal on Computing 28(6), 2150–2167 (1999)

House, D.H., Kocmoud, C.J.: Continuous cartogram construction. In: IEEE Visualization, pp. 197–204 (1998)

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)

Liao, C.C., Lu, H.I., Yen, H.C.: Compact floor-planning via orderly spanning trees. Journal of Algorithms 48, 441–451 (2003)

Raisz, E.: The rectangular statistical cartogram. Geographical Review 24(3), 292–296 (1934)

Sun, Y., Sarrafzadeh, M.: Floorplanning by graph dualization: L-shaped modules. Algorithmica 10(6), 429–456 (1993)

Tobler, W.: Thirty five years of computer cartograms. Annals of Association of American Geographers 94, 58–73 (2004)

Ungar, P.: On diagrams representing graphs. Journal of London Mathematical Society 28, 336–342 (1953)

Yeap, K.H., Sarrafzadeh, M.: Floor-planning by graph dualization: 2-concave rectilinear modules. SIAM Journal on Computing 22, 500–526 (1993)