Abstract
We give anO(|V(G)|)-time algorithm to assign vertical and horizontal segments to the vertices of any bipartite plane graphG so that (i) no two segments have an interior point in common, and (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 Petrovič. The edges of any maximal bipartite plane graphG with outer facebwb′w′ can be colored by two colors such that the color classes form spanning trees ofG−b andG−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.
Article PDF
Similar content being viewed by others
References
[DLR] G. DiBattista, W. P. Liu, and I. Rival: Bipartite graphs, drawings and planarity,Inform. Process. Lett. 36 (1990), 317–322.
[E] J. Ebert:st-ordering of the vertices of biconnected graphs,Computing 30 (1983), 19–33.
[EET] G. Ehrlich, S. Even, and R. E. Tarjan: Intersection graphs of curves on the plane.J. Combin. Theory Ser. B 21 (1976), 8–20.
[ET] S. Even and R. E. Tarjan: Computing anst-numbering.Theoret. Comput. Sci. 2 (1976), 339–344.
[FMP] H. de Fraysseix, P. O. de Mendez, and J. Pach: Representation of planar graphs by segments, in:Intuitive Geometry (K. Böröczky and G. Fejes Tóth, eds.), Colloquia Mathematica Societatis J. Bolyai, North-Holland, Amsterdam, to appear.
[FMR] H. de Fraysseix, P. O. de Mendez, and P. Rosenstiehl: Bipolar orientations revisited,Discrete Math., to appear.
[FPP] H. De Fraysseix, J. Pach, and R. Pollack: How to draw a planar graph on a grid,Combinatorica 10 (1990), 41–51.
[FRU] S. Földes, I. Rival, and J. Urrutia: Light sources, obstructions and spherical orders,Discrete Math. 102 (1992), 13–23.
[HNZ] I. B.-A. Hartman, I. Newman, and R. Ziv: On grid intersection graphs,Discrete Math. 87 (1991), 41–52.
[LEC] A. Lempel, S. Even, and I. Cederbaum: An algorithm for planarity testing of graphs, in:Theory of Graphs (Internat. Symp., Rome, July 1996, P. Rosenstiehl, ed.), Gordon and Breach, New York, 1967, pp. 215–232.
[OW] R. H. J. M. Otten and J. G. van Wijk: Graph representations in interactive layout design,Proc. IEEE Internat. Symp. on Circuits and Systems, 1978, pp. 914–918.
[P1] V. Petrovič: Decomposition of some planar graphs into trees,Proc. Internat. Conf. on Combinatorics, Keszthely, 1993, p. 48.
[P2] C. R. Platt: Planar lattices and planar graphs.J. Combin. Theory Ser. B 21 (1976), 30–39.
[R1] G. Ringel: Two trees in maximal planar bipartite graphs.J. Graph Theory 17 (1993), 755–758.
[R2] I. Rival: Graphical data structures for ordered sets, in:Algorithms and Order (I. Rival, ed.), NATO ASI Series C, Vol. 255, Kluwer, Dordrecht, 1989.
[R3] P. Rosentiehl: Embedding in the plane with orientation constraints: the angle graph,Ann. N.Y. Acad. Sci. 1983, pp. 340–346.
[RT] P. Rosentiehl and R. E. Tarjan: Rectilinear planar layouts and bipolar orientations of planar graphs.Discrete Comput. Geom. 1 (1986), 343–353.
[T1] 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, Vol. 317. Springer-Verlag, Berlin, 1988, pp. 576–590.
[TT1] R. Tamassia and I. G. Tollis: A unified approach to visibility representations of planar graphs.Discrete Comput. Geom. 1 (1986), 321–341.
[TT2] 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, Vol. 246, Springer-Verlag, Berlin, 1987, pp. 252–263.
[TT3] R. Tamassia and I. G. Tollis: Tessellation representations of planar graphs,Proc. 27th Allerton Conf. on Communications, Control, and Computing, 1989, pp. 48–57.
[T2] R. E. Tarjan Two streamlined depth-first search algorithms,Fund. Inform. 9 (1986), 85–94.
[W] H. Whitney: On the classification of graphs,Amer. J. Math. 55 (1933), 236–244.
Author information
Authors and Affiliations
Additional information
The research of H. de Fraysseix and P. O. de Mendez was supported by ESPRIT Basic Research Action No. 7141 (ALCOM II). J. Pach's research was supported by NSF Grant CCR-91-22103, OTKA-4269, and ALCOM II.
Rights and permissions
About this article
Cite this article
de Fraysseix, H., de Mendez, P.O. & Pach, J. A left-first search algorithm for planar graphs. Discrete Comput Geom 13, 459–468 (1995). https://doi.org/10.1007/BF02574056
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574056