TY - GEN
T1 - On touching triangle graphs
AU - Gansner, Emden R.
AU - Hu, Yifan
AU - Kobourov, Stephen G.
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=79952253473&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79952253473&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-18469-7_23
DO - 10.1007/978-3-642-18469-7_23
M3 - Conference contribution
AN - SCOPUS:79952253473
SN - 9783642184680
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 250
EP - 261
BT - Graph Drawing - 18th International Symposium, GD 2010, Revised Selected Papers
T2 - 18th International Symposium on Graph Drawing, GD 2010
Y2 - 21 September 2010 through 24 September 2010
ER -