Planar Drawings of Higher-Genus Graphs

Duncan, Christian A. and Goodrich, Michael T. and Kobourov, Stephen G. (2010) Planar Drawings of Higher-Genus Graphs. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 45-56 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_7).

Full text not available from this repository.

Abstract

In this paper, we give polynomial-time algorithms that can take a graph G with a given combinatorial embedding on an orientable surface S of genus g and produce a planar drawing of G in R2 , with a bounding face defined by a polygonal schema P for S. Our drawings are planar, but they allow for multiple copies of vertices and edges on P’s boundary, which is a common way of visualizing higher-genus graphs in the plane. As a side note, we show that it is NP-complete to determine whether a given graph embedded in a genus-g surface has a set of 2g fundamental cycles with vertex-disjoint interiors, which would be desirable from a graph-drawing perspective.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_7
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.560 Geometry
ID Code:1079

Repository Staff Only: item control page

References

Chen, J., Kanchi, S.P., Kanevsky, A.: A note on approximating graph genus. Information Processing Letters 61(6), 317–322 (1997)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

Duncan, C.A., Goodrich, M.T., Kobourov, S.G.: Planar drawings of higher-genus graphs. Technical report (August 2009), http://arxiv.org/abs/0908.1608

Eppstein, D.: The topology of bendless three-dimensional orthogonal graph drawing. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 78–89. Springer, Heidelberg (2009)

Erickson, J., Har-Peled, S.: Optimally cutting a surface into a disk. In: Proc. of the 18th ACM Symp. on Computational Geometry (SCG), pp. 244–253 (2002)

Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods 4(3), 312–316 (1983)

Kocay, W., Neilson, D., Szypowski, R.: Drawing graphs on the torus. Ars Combinatoria 59, 259–277 (2001)

Lazarus, F., Pocchiola, M., Vegter, G., Verroust, A.: Computing a canonical polygonal schema of an orientable triangulated surface. In: Proc. of the 17th ACM Symp. on Computational Geometry (SCG), pp. 80–89 (2001)

Miura, K., Nakano, S.-I., Nishizeki, T.: Grid drawings of 4-connected plane graphs. Discrete and Computational Geometry 26(1), 73–87 (2001)

Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins U. Press, Baltimore (2001)

Thomassen, C.: The graph genus problem is NP-complete. J. Algorithms 10(4), 568–576 (1989)

Tutte, W.T.: Convex representations of graphs. Proceedings London Mathematical Society 10(38), 304–320 (1960)

Tutte, W.T.: How to draw a graph. Proc. Lon. Math. Soc. 13(52), 743–768 (1963)

Vodopivec, A.: On embeddings of snarks in the torus. Discrete Mathematics 308(10), 1847–1849 (2008)

Zitnik, A.: Drawing graphs on surfaces. SIAM J. Disc. Math. 7(4), 593–597 (1994)