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 , pp. 199-210(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...).

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
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1310

Actions (login required)

View Item