A Left-First Search Algorithm for Planar Graphs

De Fraysseix, Hubert and Ossona de Mendez, Patrice and Pach, János (1995) A Left-First Search Algorithm for Planar Graphs. [Journal (Paginated)]

Full text not available from this repository.

Abstract

We give an O(|V(G)|)-time algorithm to assign vertical and horizontal segments to the vertices of any bipartite plane graph G so that (i) no two segments have an interior point in common, (ii) two segments touch each other if and only if the corresponding vertices are adjacent. As a corollary, we obtain a strengthening of the following theorem of Ringel and Petrovic. The edges of any maximal bipartite plane graph G with outer face bwb'w' can be colored by two colors such that the color classes form spanning trees of G-b and G-b', respectively. Furthermore, such a coloring can be found in linear time. Our method is based on a new linear-time algorithm for constructing bipolar orientations of 2-connected plane graphs.

Item Type:Journal (Paginated)
Additional Information:10.1007/BF02574056
Classifications:Z Theory > Z.500 Representations
P Styles > P.999 Others
G Algorithms and Complexity > G.999 Others
ID Code:669

Repository Staff Only: item control page

References

G. DiBattista, W. P. Liu and I. Rival: Bipartite graphs, drawings and planarity, Information Processing Letters 36 (1990), 317-322.

J.Ebert: st-ordering of the vertices of biconnected graphs, Computing 30 (1983), 19-33.

S. Even and R. E. Tarjan: Computing an st-numbering, Theoret. Comput. Sci. 2 (1976) 339-344.

G. Ehrlich, S. Even and R. E. Tarjan: Intersection graphs of curves on the plane, J. Combinat. Theory Ser B 21 (1976), 8-20.

H. de Fraysseix, J. Pach and R. Pollack: How to draw a planar graph on a grid, Combinatorica 10 (1990) 41-51.

S. Földes, I. Rival and J. Urrutia: Light sources, obstructions and spherical orders, Discrete Mathematics 102 (1992), 13-23.

I.B.-A. Hartman,I. Newman and R. Ziv: On grid intersection graphs, Discrete Math. 87 (1991) 41-52.

A. Lempel, S. Even and I. Cederbaum: An algorithm for planarity testing of graphs, in: Theory of Graphs (Intl. Symp., Rome, July 1966, P. Rosenstiehl, ed.), Gordon and Breach, New York, 1967, 215-232.

R. H. J. M. Otten and J. G. van Wijk: Graph representations in interactive layout design, Proc. IEEE Intl. Symp. on Circuits and Systems, 1978, 914-918.

C. R. Platt: Planar lattices and planar graphs, J. Combinat. Theory Ser B, 21 (1976), 30-39.

I. Rival: Graphical data structures for ordered sets, in: Algorithms and Order (I. Rival, ed.), NATO ASI Series C, Vol. 255, Kluwer Academic Publishers, 1989.

P. Rosenstiehl: Embedding in the plane with orientation constraints: The angle graph, Ann. N.Y. Acad. Sci., 340-346.

P. Rosentiehl and R. E. Tarjan: Rectilinear planar layouts and bipolar orientations of planar graphs, Discrete Comput. Geom. 1 (1986) 343-353.

R. Tamassia: A dynamic data structure for planar graph embedding, in: Automata, Languages and Programming (T. Lepistö and A. Salomaa, eds.), Lecture Notes in Computer Science 317 (1988) 576-590.

R. E. Tarjan: Two streamlined depth-first search algorithms, Fund. Inform. 9 (1986) 85-94.

R. Tamassia and I. G. Tollis: A unified approach to visibility representations of planar graphs, Discrete Comput. Geom. 1 (1986) 321-241.

R. Tamassia and I. G. Tollis: Centipede graphs and visibility on a cylinder, in: Graph-Theoretic Concepts in Computer Science (G. Tinhofer and G. Schmidt, eds.), Lecture Notes in Computer Science 246 (1987) 252-263.

H. Whitney: On the classification of graphs, Amer. J. Math. 55 (1933), 236-244.