Touching Triangle Representations for 3-Connected Planar GraphsKobourov, 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.
Official URL: http://link.springer.com/chapter/10.1007/978-3-642...
AbstractA 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.
Actions (login required)
|