TY - GEN
T1 - Planar drawings of higher-genus graphs
AU - Duncan, Christian A.
AU - Goodrich, Michael T.
AU - Kobourov, Stephen G.
PY - 2010
Y1 - 2010
N2 - In this paper, we give polynomial-time algorithms that can take a graph G with a given combinatorial embedding on an orientable surface of genus g and produce a planar drawing of G in R2, with a bounding face defined by a polygonal schema for P for S. Our drawings are planar, but they allow for multiple copies of vertices and edges on '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.
AB - In this paper, we give polynomial-time algorithms that can take a graph G with a given combinatorial embedding on an orientable surface of genus g and produce a planar drawing of G in R2, with a bounding face defined by a polygonal schema for P for S. Our drawings are planar, but they allow for multiple copies of vertices and edges on '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.
UR - https://www.scopus.com/pages/publications/77951614354
UR - https://www.scopus.com/pages/publications/77951614354#tab=citedBy
U2 - 10.1007/978-3-642-11805-0_7
DO - 10.1007/978-3-642-11805-0_7
M3 - Conference contribution
SN - 3642118046
SN - 9783642118043
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 45
EP - 56
BT - Graph Drawing - 17th International Symposium, GD 2009, Revised Papers
T2 - 17th International Symposium on Graph Drawing, GD 2009
Y2 - 22 September 2009 through 25 September 2009
ER -