Non-Convex Representations of Graphs

Di Battista, Giuseppe and Frati, Fabrizio and Patrignani, Maurizio (2009) Non-Convex Representations of Graphs. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 390-395 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_38).

Full text not available from this repository.

Abstract

We show that every plane graph admits a planar straight-line drawing in which all faces with more than three vertices are non-convex polygons

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_38
Classifications:P Styles > P.720 Straight-line
P Styles > P.540 Planar
ID Code:927

Repository Staff Only: item control page

References

Aichholzer, O., Rote, G., Schulz, A., Vogtenhuber, B.: Pointed drawings of planar graphs. In: Bose, P. (ed.) CCCG 2007. pp. 237–240 (2007)

Barany, I., Rote, G.: Strictly convex drawings of planar graphs. Doc. Math. 11, 369–391 (2006)

Chiba, N., Yamanouchi, T., Nishizeki, T.: Linear algorithms for convex drawings of planar graphs. In: Bondy, J.A., Murty, U.S.R. (eds.) Progress in Graph Theory, pp. 153–173. Academic Press, New York, NY (1984)

Chrobak, M., Goodrich, M.T., Tamassia, R.: Convex drawings of graphs in two and three dimensions. In: Symposium on Computational Geometry. pp. 319–328 (1996)

Di Battista, G., Frati, F., Patrignani, M.: Non-convex representations of graphs. Tech. Report RT-DIA-134-2008, Dip. Informatica e Automazione, Univ. Roma Tre (2008)

Fary, I.: On straight line representations of planar graphs. Acta. Sci. Math. 11, 229–233 (1948)

Haas, R., Orden, D., Rote, G., Santos, F., Servatius, B., Servatius, H., Souvaine, D., Streinu, I., Whiteley, W.: Planar minimally rigid graphs and pseudo-triangulations. Comput. Geometry Theory Appl. 31, 31–61 (2005)

Hong, S., Nagamochi, H.: Convex drawings of graphs with non-convex boundary. In: Fomin, F. (ed.) WG 2006. LNCS, vol. 4271, pp. 113–124. Springer, Heidelberg (2006)

Hong, S., Nagamochi, H.: Star-shaped drawings of planar graphs. In: Brankovich, L., Lin, Y., Smyth, W.F. (eds.) IWOCA 2007. College Publications (2007)

Hong, S., Nagamochi, H.: Star-shaped drawing of planar graphs with fixed embedding and concave corner constraints. In: Hu, X., Wang, J. (eds.) COCOON 2008. LNCS, vol. 5092, pp. 405–414. Springer, Heidelberg (2008)

Thomassen, C.: Plane representations of graphs. In: Progress in Graph Theory, pp. 43–69. Academic Press (1984)

Tutte, W.T.: Convex representations of graphs. Proc. London Math. Soc. 10, 304–320 (1960)