Graph Embedding with Topological Cycle-Constraints

Dornheim, Christoph (1999) Graph Embedding with Topological Cycle-Constraints. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999 , pp. 155-164(Official URL:

Full text not available from this repository.


This paper concerns graph embedding under topological constraints. We address the problem of finding a planar embedding of a graph satisfying a set of constraints between its vertices and cycles that require embedding a given vertex inside its corresponding cycle. This problem turns out to be NP-complete. However, towards an analysis of its tractable subproblems, we develop an efficient algorithm for the special case where graphs are 2-connected and any two distinct cycles in the constraints have at most one vertex in common.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-46648-7_16
Classifications: G Algorithms and Complexity > G.490 Embeddings
Z Theory > Z.750 Topology
G Algorithms and Complexity > G.770 Planarity Testing

Actions (login required)

View Item View Item