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. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/978-3-642-18469-7_23 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
touching triangles representation,outerplanar graph,linear time algorithm,triangles representation,biconnected graph,square grid graph,sides touch,small common neighborhood,complete characterization,triangle graph,hexagonal grid graph | Conference | abs/1001.2862 |
ISSN | Citations | PageRank |
0302-9743 | 4 | 0.48 |
References | Authors | |
16 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Emden R. Gansner | 1 | 1117 | 115.32 |
Yifan Hu | 2 | 1480 | 88.96 |
Stephen G. Kobourov | 3 | 1440 | 122.20 |