Algorithmic graph embeddings Academic Article uri icon

abstract

  • The complexity of embedding a graph into a variety of topological surfaces is investigated. A new data structure for graph embeddings is introduced and shown to be superior to the previously known data structures. In particular, the new data structure efficiently supports all on-line operations for general graph embeddings. Based on this new data structure, very efficient algorithms are developed to solve the problem "given a graph G and an integer k, construct a genus k embedding for the graph G" for a large range of integers k and for a large class of graphs G.

published proceedings

  • THEORETICAL COMPUTER SCIENCE

author list (cited authors)

  • Chen, J.

citation count

  • 21

complete list of authors

  • Chen, J

publication date

  • July 1997