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, Štirín Castle, Czech Republic , pp. 155-164 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_16).

Full text not available from this repository.

Abstract

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
ID Code:324

Repository Staff Only: item control page

References

J. A. Bondy, U. S. R. Murty: Graph Theory with Applications, MacMillan, 1976

G. Demoucron, Y. Malgrange, R. Pertuiset: Graphes planaires: reconnaissance et construction de représentations planaires topologiques, Revue Francaise de Recherche Opérationelle, 8:33-47, 1964.

R. Diestel: Graph Theory, Springer, 1997

M. R. Garey, D. S. Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness, Freeman, 1979

W. He, K. Marriott: Constrained graph layout, in S. North (ed.), Graph Drawing, Proceedings of GD'96, LNCS 1190, 217-232, 1997

M. M. Syslo: An efficient cycle vector space algorithm for listing all cycles of a planar graph, SIAM Journal on Computing, 10,4:797-808, 1981

R. Tamassia. Constraints in graph drawing algorithms, Constraints, 3:87-120, 1998

C. Thomassen: Planarity and duality of finite and infinite graphs, Journal of Combinatorial Theory, Series B, 29: 244-271, 1980