Edge-Weighted Contact Representations of Planar Graphs

Nöllenburg, Martin and Prutkin, Roman and Rutter, Ignaz (2013) Edge-Weighted Contact Representations of Planar Graphs. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 224-235 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_20).

Full text not available from this repository.

Abstract

We study contact representations of edge-weighted planar graphs, where vertices are rectangles or rectilinear polygons and edges are polygon contacts whose lengths represent the edge weights. We show that for any given edge-weighted planar graph whose outer face is a quadrangle, that is internally triangulated and that has no separating triangles we can construct in linear time an edge-proportional rectangular dual if one exists and report failure otherwise. For a given combinatorial structure of the contact representation and edge weights interpreted as lower bounds on the contact lengths, a corresponding contact representation that minimizes the size of the enclosing rectangle can be found in linear time.If the combinatorial structure is not fixed, we prove NP-hardness of deciding whether a contact representation with bounded contact lengths exists. Finally, we give a complete characterization of the rectilinear polygon complexity required for representing biconnected internally triangulated graphs: For outerplanar graphs complexity 8 is sufficient and necessary, and for graphs with two adjacent or multiple non-adjacent internal vertices the complexity is unbounded.

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

Repository Staff Only: item control page

References

Alam, M.J., Biedl, T., Felsner, S., Gerasch, A., Kaufmann, M., Kobourov, S.G.: Linear-Time Algorithms for Hole-Free Rectilinear Proportional Contact Graph Representations. In: Asano, T., Nakano, S.-i., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 281–291. Springer, Heidelberg (2011)

Alam, M.J., Biedl, T., Felsner, S., Kaufmann, M., Kobourov, S.G., Ueckerdt, T.: Computing cartograms with optimal complexity. In: Proc. 28th ACM Symp. on Computational Geometry, SoCG 2012, pp. 21–30. ACM (2012)

Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall (1999)

de Berg, M., Mumford, E., Speckmann, B.: On rectilinear duals for vertex-weighted plane graphs. Discrete Mathematics 309(7), 1794–1812 (2009)

Biedl, T., Genc, B.: Complexity of octagonal and rectangular cartograms. In: Proc. 17th Canadian Conference on Computational Geometry, CCCG 2005, pp. 117–120 (2005)

Biedl, T., Ruiz Velázquez, L.E.: Orthogonal Cartograms with Few Corners Per Face. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 98–109. Springer, Heidelberg (2011)

Cabello, S., Demaine, E.D., Rote, G.: Planar embeddings of graphs with specified edge lengths. J. Graph Algorithms Appl. 11(1), 259–276 (2007)

Chalopin, J., Gonçalves, D.: Every planar graph is the intersection graph of segments in the plane. In: Proc. 41st Ann. ACM Symp. Theory of Computing, STOC 2009, pp. 631–638. ACM (2009)

Eades, P., Wormald, N.C.: Fixed edge-length graph drawing is NP-hard. Discrete Applied Mathematics 28(2), 111–134 (1990)

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 finding the rectangular duals of planar triangular graphs. SIAM J. Comput. 22(6), 1218–1226 (1993)

Hliněný, P., Kratochvíl, J.: Representing graphs by disks and balls (a survey of recognition-complexity results). Discrete Mathematics 229(1-3), 101–124 (2001)

Kawaguchi, A., Nagamochi, H.: Orthogonal Drawings for Plane Graphs with Specified Face Areas. In: Cai, J.-Y., Cooper, S.B., Zhu, H. (eds.) TAMC 2007. LNCS, vol. 4484, pp. 584–594. Springer, Heidelberg (2007)

Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discrete Math. 5(3), 422–427 (1992)

Koebe, P.: Kontaktprobleme der konformen abbildung. Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Klasse 88, 141–164 (1936)

Kozminski, K.A., Kinnen, E.: Rectangular dualization and rectangular dissections. IEEE Trans. Circuits and Systems 35(11), 1401–1416 (1988)

van Kreveld, M., Speckmann, B.: On rectangular cartograms. Comput. Geom. Theory Appl. 37(3), 175–187 (2007)

Leinwand, S.M., Lai, Y.T.: An algorithm for building rectangular floor-plans. In: Proc. 21st Design Automation Conference, pp. 663–664 (1984)

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

Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)

McKee, T.A., McMorris, F.R.: Topics in Intersection Graph Theory. SIAM (1999)

Nishizeki, T., Rahman, M.S.: Rectangular drawing algorithms. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, ch. 13. CRC Press (2013) (to appear)

Tamassia, R.: Drawing algorithms for planar st-graphs. Australasian J. Combinatorics 2, 217–235 (1990)

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