Graph Embedding with Topological CycleConstraintsDornheim, Christoph (1999) Graph Embedding with Topological CycleConstraints. In: Graph Drawing 7th International Symposium, GD’99, September 1519, 1999 , pp. 155164(Official URL: http://dx.doi.org/10.1007/3540466487_16). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540466487_16
AbstractThis 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 NPcomplete. However, towards an analysis of its tractable subproblems, we develop an efficient algorithm for the special case where graphs are 2connected and any two distinct cycles in the constraints have at most one vertex in common.
Actions (login required)
