Show simple item record

dc.contributor.authorDjidjev, Hristo N.
Venkatesan, Shankar M.
dc.date.accessioned 2017-08-02T22:03:28Z
dc.date.available 2017-08-02T22:03:28Z
dc.date.issued 1995-06-02
dc.identifier.urihttps://hdl.handle.net/1911/96456
dc.description.abstract A planarizing set of a graph is a set of edges or vertices whose removal leaves a planar graph. It is shown that if G is an n vertex graph of maximum degree d and orientable genus g, then there exists a planarizing set of O(sqrt(dgn)) edges. This result is tight within a constant factor. Similar results are obtained for planarizing vertex sets and for graphs embedded on nonorientable surfaces. Planarizing edge and vertex sets can be found in O(n+g) time if an embedding of G on a surface of genus g is given. We also construct an approximation algorithm that finds an O(sqrt(gn log g)) planarizing vertex set of G in O(n log g) time if no genus g embedding is given as an input.
dc.format.extent 10 pp
dc.language.iso eng
dc.rights You are granted permission for the noncommercial reproduction, distribution, display, and performance of this technical report in any format, but this permission is only for a period of forty-five (45) days from the most recent time that you verified that this technical report is still available from the Computer Science Department of Rice University under terms that include this permission. All other rights are reserved by the author(s).
dc.title Planarization of Graphs Embedded on Surfaces
dc.type Technical report
dc.date.note June 2, 1995
dc.identifier.digital TR96-260
dc.type.dcmi Text
dc.identifier.citation Djidjev, Hristo N. and Venkatesan, Shankar M.. "Planarization of Graphs Embedded on Surfaces." (1995) https://hdl.handle.net/1911/96456.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record