Name
Abstract | ||
|---|---|---|
A straight-line drawing of a plane graph is called an open rectangle-of-influence drawing if there is no vertex in the proper inside of the axis-parallel rectangle defined by the two ends of every edge. In an inner triangulated plane graph, every inner face is a triangle although the outer face is not always a triangle. In this paper, we first obtain a sufficient condition for an inner triangulated plane graph G to have an open rectangle-of-influence drawing; the condition is expressed in terms of a labeling of angles of a subgraph of G. We then present an O(n1.5/log n)-time algorithm to examine whether G satisfies the condition and, if so, construct an open rectangle-of-influence drawing of G on an (n-1)×(n-1) integer grid, where n is the number of vertices in G. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/978-3-540-70904-6_15 | GD'06 Proceedings of the 14th international conference on Graph drawing |
Keywords | Field | DocType |
open rectangle-of-influence drawing,inner triangulated plane graph,straight-line drawing,inner face,plane graph,sufficient condition,log n,outer face,axis-parallel rectangle,integer grid | Geometric graph theory,Discrete mathematics,Outerplanar graph,Combinatorics,Crossing number (graph theory),Slope number,Graph power,Cycle graph,Dominance drawing,Mathematics,Planar graph | Conference |
Volume | Issue | ISSN |
4372 | 4 | 0302-9743 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kazuyuki Miura | 1 | 84 | 8.66 |
| Tetsuya Matsuno | 2 | 3 | 1.20 |
| Takao Nishizeki | 3 | 1771 | 267.08 |