Touching Triangle Representations for 3-Connected Planar Graphs

Kobourov, Stephen G. and Mondal, Debajyoti and Nishat, Rahnuma Islam (2013) Touching Triangle Representations for 3-Connected Planar Graphs. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 199-210 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_18).

Full text not available from this repository.

Abstract

A touching triangle graph (TTG) representation of a planar graph is a planar drawing Γ of the graph, where each vertex is represented as a triangle and each edge e is represented as a side contact of the triangles that correspond to the end vertices of e. We call Γ a proper TTG representation if Γ determines a tiling of a triangle, where each tile corresponds to a distinct vertex of the input graph. In this paper we prove that every 3-connected cubic planar graph admits a proper TTG representation. We also construct proper TTG representations for parabolic grid graphs and the graphs determined by rectangular grid drawings (e.g., square grid graphs). Finally, we describe a fixed-parameter tractable decision algorithm for testing whether a 3-connected planar graph admits a proper TTG representation.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_18
Classifications:P Styles > P.720 Straight-line
Z Theory > Z.500 Representations
ID Code:1310

Repository Staff Only: item control page

References

Batagelj, V.: Inductive classes of cubic graphs. In: Proceedings of the 6th Hungarian Colloquium on Combinatorics, Eger, Hungary. Finite and infinite sets, vol. 37, pp. 89–101 (1981)

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

de Fraysseix, H., de Mendez, P.O.: Barycentric systems and stretchability. Discrete Applied Mathematics 155(9), 1079–1095 (2007)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10, 41–51 (1990)

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

Duncan, C., Gansner, E.R., Hu, Y., Kaufmann, M., Kobourov, S.G.: Optimal polygonal representation of planar graphs. Algorithmica 63(3), 672–691 (2012)

Gansner, E.R., Hu, Y., Kobourov, S.G.: On Touching Triangle Graphs. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 250–261. Springer, Heidelberg (2011)

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

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)

Phillips, R.: The Order-5 triangle partitions, http://www.mathpuzzle.com/triangle.html (accessed June 7, 2012)

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

Thomassen, C.: Interval representations of planar graphs. Journal of Combinatorial Theory (B) 40(1), 9–20 (1986)

Woeginger, G.J.: Exact Algorithms for NP-Hard Problems: A Survey. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol. 2570, pp. 185–207. Springer, Heidelberg (2003)