Open Rectangle-of-Influence Drawings of Inner Triangulated Plane Graphs

Miura, Kazuyuki and Matsuno, Tetsuya and Nishizeki, Takao (2007) Open Rectangle-of-Influence Drawings of Inner Triangulated Plane Graphs. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 138-149 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_15).

Full text not available from this repository.

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(n^{1.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) x (n-1) integer grid, where n is the number of vertices in G.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_15
Classifications:P Styles > P.720 Straight-line
ID Code:769

Repository Staff Only: item control page

References

T. Biedl, A. Bretscher and H. Meijer, Rectangle of influence drawings of graphs without filled 3-cycles, Proceedings of Graph Drawing 1999, LNCS 1731, Springer, pp. 359-368, 2000.

T. Biedl, G. Kant, and M. Kaufmann, On triangulating planar graphs under the four-connectivity constraint, Algorithmica, 19, 4, pp. 427-446, 1997.

M. Chrobak and G. Kant, Convex grid drawings of 3-connected planar graphs, Int. J. Comput. Geom Appl., 7, 3, pp. 211-223, 1997.

G. Di Battista, P. Eades, R. Tamassia and I. G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice-Hall, Upper Saddle River, NJ 07458, 1999.

G. Di Battista, W. Lenhart and G. Liotta, Proximity drawability:A survey, Proc. Graph Drawing 1994, Lect. Note in Computer Science, LNCS, Number 894, pp. 328-339, Springer-Verlag, 1995.

H. de Fraysseix, J. Pach, R. Pollack, How to draw a graph on a grid, Combinatorica, 10, pp. 41-51, 1990.

F. Harary, Graph Theory, Addison-Wesley, Reading, Massachusetts, 1969.

D. S. Hochbaum, Faster pseudoflow-based algorithms for the bipartite matching and the closure problems, Abstract, CORS/SCRO-INFORMS Joint Int. Meeting, Ban, Canada, p. 46, May 16-19, 2004.

D. S. Hochbaum and B. G. Chandran, Further below the flow decomposition barrier of maximum flow for bipartite matching and maximum closure, Working paper, 2004.

G. Kant and X. He, Regular edge-labeling of 4-connected plane graphs and its applications in graph drawing problems, Theoretical Computer Science, 172, pp.175-193, 1997.

G. Liotta, A. Lubiw, H. Meijer and S. H. Whitesides, The rectangle of influence drawability problem, Comput. Geom. Theory and Applications, 10, 1, pp.1-22, 1998.

K. Miura and T. Nishizeki, Rectangle-of-influence drawings of four-connected plane graphs, Proc. of Information Visualisation 2005, Asia-Pacic Symposium on Information Visualisation (APVIS2005), ACS Vol 45, pp.71-76, 2005.

K. Miura, S. Nakano and T. Nishizeki, Grid drawings of four-connected plane graphs, Discrete & Computational Geometry, 26, 1, pp.73-87, 2001.

T. Nishizeki and Md. S. Rahman, Planar Graph Drawing, World Scientic, Singapore, 2004.

W. Schnyder, Embedding planar graphs in the grid, Proc. 1st Annual ACM-SIAM Symp. on Discrete Algorithms, San Francisco, pp.138-147, 1990.