Planar Open Rectangle-of-Influence Drawings with Non-aligned Frames

Alamdari, Soroush and Biedl, Therese (2012) Planar Open Rectangle-of-Influence Drawings with Non-aligned Frames. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 14-25 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_3).

Full text not available from this repository.

Abstract

A straight-line drawing of a graph is an open weak rectangle-of-influence (RI) drawing, if there is no vertex in the relative interior of the axis-parallel rectangle induced by the end points of each edge. No algorithm is known to test whether a graph has a planar open weak RI-drawing, not even for inner triangulated graphs. In this paper, we study RI-drawings that must have a non-aligned frame, i.e., the graph obtained from removing the interior of every filled triangle is drawn such that no two vertices have the same coordinate. We give a polynomial algorithm to test whether an inner triangulated graph has a planar open weak RI-drawing with non-aligned frame.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_3
Classifications:P Styles > P.999 Others
ID Code:1237

Repository Staff Only: item control page

References

Alamdari, S., Biedl, T.: Planar Open Rectangle-of-Influence Drawings with Non-Aligned Frames. Technical Report CS-2011-17, David R. Cheriton School of Computer Science, University of Waterloo (2011)

Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1998)

Biedl, T.C., Bretscher, A., Meijer, H.: Rectangle of Influence Drawings of Graphs without Filled 3-Cycles. In: Kratochvíl,J. (ed.) GD 1999. LNCS, vol. 1731, pp.359–368. Springer, Heidelberg (1999)

Fusy, E.: Transversal structures on triangulations: A combinatorial study and straight-line drawings. Discrete Mathematics 309(7), 1870–1894 (2009)

Goldberg, A.V., Rao, S.: Beyond the flow decomposition barrier. J. ACM 45, 783–797 (1998)

Kozminski, K., Kinnen, E.: Rectangular dual of planar graphs. Networks 5, 145–157 (1985)

Leinwand, S.M., Lai, Y.-T.: An algorithm for building rectangular floor-plans. In:21st Design Automation Conference, pp. 663–664. IEEE Press (1984)

Liotta, G., Lubiw, A., Meijer, H., Whitesides, S.H.: The rectangle of influence drawability problem. Computational Geometry 10(1), 1–22 (1998)

Miura, K., Haga, H., Nishizeki, T.: Inner rectangular drawings of plane graphs. Int. J. Comput. Geometry Appl. 16(2-3), 249–270 (2006)

Miura, K., Matsuno, T., Nishizeki, T.: Open rectangle-of-influence drawings of inner triangulated plane graphs. Discrete & Computational Geometry 41(4), 643–670 (2009)

Miura, K., Nishizeki, T.: Rectangle-of-influence drawings of four-connected plane graphs. In: Asia-Pacific Symposium on Information Visualization (APVIS). CR-PIT, vol. 45, pp. 75–80 (2005)

Sadasivam, S., Zhang, H.: Closed rectangle-of-influence drawings for irreducible triangulations. Comput. Geom. Theory Appl. 44, 9–19 (2011)

Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16, 421–444 (1987)

Ungar, P.: On diagrams representing maps. J. London Mathematical Society 28(3),336–342 (1953)

Zhang, H., Vaidya, M.: On open rectangle-of-influence and rectangular dual drawings of plane graphs. Discrete Mathematics, Algorithms and Applications 1, 319–333 (2009)