Abstract | ||
---|---|---|
Let x0, x1, ..., xn-1 be vertices of a convex n-gon P in the plane, where, x0x1, x1x2, ..., xn-2xn-1, and xn-1x0 are edges of P. Let G= (N, E) be a graph, such that N= {0, 1, ..., n -1}. Consider a graph drawing of Gsuch that each vertex i 驴 N is represented by xi and each edge (i, j) 驴 Eis drawn by a straight line segment. Denote the sum of lengths of graph edges in such drawing by SP(G). If SP(G) 驴 SP(G驴) for any convex n-gon P, then we write as G 驴i G驴. This paper shows two necessary and sufficient conditions of G 驴i G驴. Moreover, these conditions can be calculated in polynomial time for any given G and G驴. |
Year | DOI | Venue |
---|---|---|
2000 | 10.1007/3-540-47738-1_14 | JCDCG |
Keywords | Field | DocType |
sufficient condition,i g,graph edge,graph drawn,graph drawing,convex polygon,edge lengths,polynomial time,vertex i,convex n-gon p,convex n-gon,straight line segment | Discrete mathematics,Combinatorics,Edge-transitive graph,Bound graph,Graph power,Neighbourhood (graph theory),Cycle graph,Graph minor,Mathematics,Complement graph,Path graph | Conference |
Volume | ISSN | ISBN |
2098 | 0302-9743 | 3-540-42306-0 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hiro Ito | 1 | 290 | 39.95 |
Hideyuki Uehara | 2 | 54 | 12.14 |
Mitsuo Yokoyama | 3 | 66 | 9.51 |