Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-27T12:01:48.906Z Has data issue: false hasContentIssue false
  • English
  • Français

Obstructions for the Disk and the Cylinder Embedding Extension Problems

Published online by Cambridge University Press:  12 September 2008

Bojan Mohar
Bojan Mohar
Affiliation:
Department of Mathematics, University of Ljubljana, Jadranska 19, 61111 Ljubljana, Slovenia email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Let S be a closed surface with boundary ∂S and let G be a graph. Let K ⊆ G be a subgraph embedded in S such that ∂S ⊆ K. An embedding extension of K to G is an embedding of G in S that coincides on K with the given embedding of K. Minimal obstructions for the existence of embedding extensions are classified in cases when S is the disk or the cylinder. Linear time algorithms are presented that either find an embedding extension, or return an obstruction to the existence of extensions. These results are to be used as the corner stones in the design of linear time algorithms for the embeddability of graphs in an arbitrary surface and for solving more general embedding extension problems.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 3 , September 1994 , pp. 375 - 406
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Archdeacon, D. and Huneke, P. (1989) A Kuratowski theorem for non-orientable surfaces. J. Combin. Theory, Ser. B 46 173–231.CrossRefGoogle Scholar
[2]Booth, K. S. and Lueker, G. S. (1976) Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. System Sci. 13 335–379.CrossRefGoogle Scholar
[3]Chiba, N., Nishizeki, T., Abe, S. and Ozawa, T. (1985) A linear algorithm for embedding planar graphs using PQ-trees. J. Comput. System Sci. 30 54–76.CrossRefGoogle Scholar
[4]Cook, S. A. and Reckhow, R. A. (1973) Time bounded random access machines. J. Comput. System Sci. 7 354–375.CrossRefGoogle Scholar
[5] de Fraysseix, H. and Rosenstiehl, P. (1982) A depth-first search characterization of planarity. Ann. Discrete Math. 13 75–80.Google Scholar
[6]Gross, J. L. and Tucker, T. W. (1987) Topological Graph Theory, Wiley-Interscience.Google Scholar
[7]Hopcroft, J. E. and Tarjan, R. E. (1973) Dividing a graph into triconnected components. SIAM J. Comput. 2 135–158.CrossRefGoogle Scholar
[8]Hopcroft, J. E. and Tarjan, R. E. (1974) Efficient planarity testing. J. Assoc. Comput. Mach. 21 549–568.CrossRefGoogle Scholar
[9]Jung, H. A. (1970) Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen. Math. Ann. 187 95–103.CrossRefGoogle Scholar
[10]Juvan, M., Marinček, J. and Mohar, B. (submitted) Embedding graphs in the torus in linear time.Google Scholar
[11]Juvan, M., Marinček, J. and Mohar, B. (in preparation) Efficient algorithm for embedding graphs in arbitrary surfaces.Google Scholar
[12]Juvan, M. and Mohar, B. (submitted) A linear time algorithm for the 2-restricted embedding extension problem.Google Scholar
[13]Karabeg, A. (1990) Classification and detection of obstructions to planarity. Linear and Multilinear Algebra 26 15–38.CrossRefGoogle Scholar
[14]MacLane, S. (1937) A structural characterization of planar combinatorial graphs. Duke Math. J. 3 460–472.Google Scholar
[15]Mohar, B. (1993) Projective planarity in linear time. J. Algorithms 15 482–502.CrossRefGoogle Scholar
[16]Mohar, B. (submitted) Universal obstructions for embedding extension problems.Google Scholar
[17]Mohar, B. (in preparation) A Kuratowski theorem for general surfaces.Google Scholar
[18]Papadimitriou, C. H. and Steiglitz, K. (1982) Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall.Google Scholar
[19]Robertson, N. and Seymour, P. D. (1990) Graph minors. VIII. A Kuratowski theorem for general surfaces. J. Combin. Theory, Ser. B 48 255–288.CrossRefGoogle Scholar
[20]Robertson, N. and Seymour, P. D. (1990) Graph minors. IX. Disjoint crossed paths. J. Combin. Theory, Ser. B 49 40–77.CrossRefGoogle Scholar
[21]Seymour, P. D. (1980) Disjoint paths in graphs. Discrete Math. 29 293–309.CrossRefGoogle Scholar
[22]Seymour, P. D. (1986) Adjacency in binary matroids. European J. Combin. 7 171–176.CrossRefGoogle Scholar
[23]Seymour, P. D. (submitted) A bound on the excluded minors for a surface.Google Scholar
[24]Shiloach, Y. (1980) A polynomial solution to the undirected two paths problem. J. Assoc. Comput. Mach. 27 445–456.CrossRefGoogle Scholar
[25]Thomassen, C. (1980) 2-linked graphs. European J. Combin. 1 371–378.CrossRefGoogle Scholar
[26]Tutte, W. T. (1966) Connectivity in Graphs, Univ. Toronto Press, Toronto, Ontario; Oxford Univ. Press, London.CrossRefGoogle Scholar
[27]Williamson, S. G. (1980) Embedding graphs in the plane – algorithmic aspects. Ann. Discrete Math. 6 349–384.CrossRefGoogle Scholar
[28]Williamson, S. G. (1984) Depth-first search and Kuratowski subgraphs. J. Assoc. Comput. Mach. 31 681–693.CrossRefGoogle Scholar