hal-00005623, version 1

A Left-First Search Algorithm for Planar Graphs.

Hubert De Fraysseix () ¹, Patrice Ossona De Mendez () ¹, Janos Pach

Discrete and Computational Geometry 13 (1995) 459-468

• 1:  Centre d'analyse et de mathématique sociale (CAMS)
• http://cams.ehess.fr/
  CNRS : UMR8557 – École des Hautes Études en Sciences Sociales [EHESS] 54 boulevard Raspail 75006 Paris France

Bibliographic reference

• Type of document: Articles in peer-reviewed journal
• Subject: Mathematics/Combinatorics
• Title: A Left-First Search Algorithm for Planar Graphs.
• 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.
• Fulltext language: English
• Production date: 1995
• Journal:

  Discrete and Computational Geometry
  Publisher	Springer Verlag (Germany)
  ISSN	0179-5376 (eISSN : 1432-0444)

• Publication date: 1995
• Volume: 13
• Page, identifiant, ...: 459-468
• Classification: 05C62, 05C85

Attached file list to this document: 

• hal-00005623, version 1
• http://hal.archives-ouvertes.fr/hal-00005623
• oai:hal.archives-ouvertes.fr:hal-00005623
• From: Patrice Ossona De Mendez <>
• Submitted on: Friday, 19 August 2005 12:11:48
• Updated on: Monday, 22 August 2005 09:44:43