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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1079

Actions (login required)

View Item View Item