# zbMATH — the first resource for mathematics

Elimination of local bridges. (English) Zbl 0958.05033
Summary: Vertices of degree different from 2 in a graph $$K$$ are called main vertices of $$K$$, and paths joining these vertices are branches of $$K$$. Let $$K$$ be a subgraph of $$G$$. It is shown that if $$G$$ is 3-connected (modulo $$K$$), then it is possible to replace branches of $$K$$ by other branches joining the same pairs of main vertices of $$K$$ such that $$G$$ has no bridges with respect to the new subgraph whose vertices of attachment all lie on a single branch of $$K$$. We present a linear time algorithm that either performs such a task, or finds a Kuratowski subgraph $$K_5$$ or $$K_{3,3}$$ in a subgraph of $$G$$ formed by a branch $$e$$ and those bridges of $$K$$ in $$G$$ that are attached only to the branch $$e$$.

##### MSC:
 05C10 Planar graphs; geometric and topological aspects of graph theory 05C85 Graph algorithms (graph-theoretic aspects) 68R10 Graph theory (including graph drawing) in computer science
##### Keywords:
algorithm; graph; embedding; bridge; Kuratowski subgraph
Full Text:
##### References:
 [1] BOOTH K. S.-LUEKER G. S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-trees. J. Comput. System Sci. 13 (1976), 335-379. · Zbl 0367.68034 [2] CHIBA N.-NISHIZEKI T.-ABE S.-OZAWA T.: A linear algorithm for embedding planar graphs using PQ-trees. J. Comput. System Sci. 30 (1985), 54-76. · Zbl 0605.68060 [3] COOK S. A.-RECKHOW R. A.: Time bounded random access machines. J. Comput. System Sci. 7 (1976), 354-375. · Zbl 0284.68038 [4] de FRAYSSEIX H.-ROSENSTIEHL P.: A depth-first search characterization of planarity. Ann. Discrete Math. 13 (1982), 75-80. · Zbl 0497.05026 [5] GROSS J. L.-TUCKER T. W.: Topological Graph Theory. Wiley-Interscience, New York, 1987. · Zbl 0621.05013 [6] HOPCROFT J. E.-TARJAN R. E.: Efficient planarity testing. J. Assoc. Comput. Mach. 21 (1974), 549-568. · Zbl 0307.68025 [7] JUVAN M.-MARINČEK J.-MOHAR B.: A linear time algorithm for embedding graphs in the torus. [8] LEMPEL A.-EVEN S.-CEDERBAUM I.: An algorithm for planarity testing of graphs. Theory of Graphs: International Symposium, Rome, July 1966 (P. Rosenstiehl, Gordon and Breach, New York, 1967, pp. 215-232. [9] MOHAR B.: Convex representations of maps on the torus and other flat surfaces. Discrete Comput. Geom. 11 (1994), 83-95. · Zbl 0791.05029 [10] MOHAR B.: A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discrete Math. · Zbl 0931.05025 [11] OHTSUKI T.: The two disjoint paths problem and wire routing design. Graph Theory and Algorithms (N. Saito, T. Nishizeki, Lecture Notes in Comput. Sci. 108, Springer,New York, 1980, pp. 207-216. [12] ROBERTSON N.-SEYMOUR P. D.: An outline of a disjoint paths algorithm. Paths, Flows, and VLSI-Layout, (B. Korte, L. Lovasz, H. J. Promel, A. Schrijver, Springer-Verlag, Berlin, 267-292. · Zbl 0759.05055 [13] VOSS H.-J.: Cycles and Bridges in Graphs. Kluwer, Dordrecht, 1991. · Zbl 0731.05031 [14] WILLIAMSON S. G.: Embedding graphs in the plane - algorithmic aspects. Ann. Discrete Math. 6 (1980), 349-384. · Zbl 0451.05021 [15] WILLIAMSON S. G.: Depth-first search and Kuratowski subgraphs. J. Assoc. Comput. Mach. 31 (1984), 681-693. · Zbl 0632.68063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.