On Touching Triangle Graphs

Gansner, Emden R. and Hu, Yifan and Kobourov, Stephen G. (2011) On Touching Triangle Graphs. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 250-261 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_23).

Full text not available from this repository.

Abstract

In this paper, we consider the problem of representing graphs by triangles whose sides touch. We present linear time algorithms for creating touching triangles representations for outerplanar graphs, square grid graphs, and hexagonal grid graphs. The class of graphs with touching triangles representations is not closed under minors, making characterization difficult. We do show that pairs of vertices can only have a small common neighborhood, and we present a complete characterization of the subclass of biconnected graphs that can be represented as triangulations of some polygon.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_23
Classifications:Z Theory > Z.250 Geometry
ID Code:1211

Repository Staff Only: item control page

References

de Berg, M., van Kreveld, M., Overmars, M.H., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 2nd edn. Springer, Heidelberg (2000)

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

Bern, M.: Triangulations. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry. CRC Press, Boca Raton (1997)

Bhasker, J., Sahni, S.: A linear algorithm to find a rectangular dual of a planar triangulated graph. Algorithmica 3, 247–278 (1988)

Brightwell, G.R., Scheinerman, E.R.: Representations of planar graphs. SIAM Journal on Discrete Mathematics 6(2), 214–229 (1993)

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

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., Rosenstiehl, P.: Representation of planar hypergraphs by contacts of triangles. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 125–136. Springer, Heidelberg (2008)

de Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting Fary embeddings of planar graphs. In: 20th Symposium on Theory of Computing (STOC), pp. 426–433 (1988)

Gansner, E., Hu, Y., Kaufmann, M., Kobourov, S.: Optimal polygonal representation of planar graphs. In: 9th LATIN Sympoisum, pp. 417–432 (2010)

Harary, F.: Graph Theory. Addison-Wesley, Reading (1972)

He, X.: On finding the rectangular duals of planar triangular graphs. SIAM Journal of Computing 22(6), 1218–1226 (1993)

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

Hopcroft, J., Tarjan, R.E.: Efficient planarity testing. Journal of the ACM 21(4), 549–568 (1974)

Kant, G.: Hexagonal grid drawings. In: 18th Workshop on Graph-Theoretic Concepts in Computer Science, pp. 263–276 (1992)

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)

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

Rahman, M., Nishizeki, T., Ghosh, S.: Rectangular drawings of planar graphs. Journal of Algorithms 50(1), 62–78 (2004)

Steinitz, E., Rademacher, H.: Vorlesungen über die Theorie der Polyeder. Springer, Berlin (1934)

Thomassen, C.: Plane representations of graphs. In: Bondy, J.A., Murty, U.S.R. (eds.) Progress in Graph Theory, pp. 43–69. Academic Press, Canada (1984)

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