Given any bipartite planar graph G, one can assign vertical and horizontal segments to its vertices so that (a) no two of them have an interior point in common, (b) two segments have a point in common if and only if the corresponding vertices are adjacent in G.

It is proved that any plane graph may be represented by a triangle contact system, that is a collection of triangular disks which are disjoint except at contact points, each contact point being a node of exactly one triangle. Representations using contacts of T- of Y-shaped objects follow. Moreover, there is a one-to-one mapping between all the triangular contact representations of a maximal plane graph and all its partitions into three Schnyder trees.

Acyclic orientations with exactly one source and one sink - the so-called bipolar orientations - arise in many graph algorithms and specially in graph drawing. The fundamental properties of these orientations are explored in terms of circuits, cocircuits and also in terms of ``angles'' in the planar case.
Classical results get here new simple proofs; new results concern the extension of partial orientations, exhaustive enumerations, the existence of deletable and contractable edges, and continuous transitions between bipolar orientations.

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.

Different areas of discrete mathematics lead to intrinsically different characterizations of planar graphs. Planarity is expressed in terms of topology, combinatorics, algebra or search trees. More recently, Schnyder's work has related planarity to partial order theory. Acyclic orientations and associated edge partial orders lead to a new characterization of planar graphs, which also describes all the possible planar embeddings. We prove here that there is a bijection between bipolar plane digraphs and 2-dimensional N-free partial orders. We give also a characterization of planarity in terms of 2-colorability of a graph and provide a short proof of a previous result on planar lattices.

A family of Jordan arcs, such that two arcs are nowhere tangent, defines a hypergraph whose vertices are the arcs and whose edges are the intersection points. We shall say that the hypergraph has a strong intersection representation and, if each intersection point is interior to at most one arc, we shall say that the hypergraph has a strong contact representation.
We first characterize those hypergraphs which have a strong contact representation and deduce some sufficient conditions for a simple planar graph to have a strong intersection representation.
Then, using the Four Color Theorem, we prove that a large class of simple planar graphs have a strong intersection representation.

The traversal of a self crossing closed plane curve, with points of multiplicity at most two, defines a double occurrence sequence, the Gauss code of the curve.
Using the D-switch operation, we give a new simple characterization of these sequences and deduce a simple self-contained proof of Rosenstiehl's characterization.

We give here three simple linear time algorithms on planar graphs: a 4-connexity test for maximal planar graphs, an algorithm enumerating the triangles and a 3-connexity test. Although all these problems got already linear-time solutions, the presented algorithms are both simple and efficient. They are based on some new theoretical results.

We are concerned with two classes of planar graphs: maximal planar graphs (i.e. polyhedral graphs, triangulations) and maximal bipartite planar graphs (i.e. bipartite planar graphs with quadrilateral faces). For these graphs we consider constrained orientations with a constant indegree for the internal vertex set. We recall or prove new fundamental relations between these orientations, specific tree decompositions and bipolar orientations. In particular, these relations yield linear time computation algorithms. Using these orientations, we give a characterization of 4-connected maximal planar graphs and 3-connected planar graphs, which leads to simple line time algorithms.

We give a characterization of DFS cotree-critical graphs which is central to the linear time Kuratowski finding algorithm implemented in PIGALE (Public Implementation of a Graph Algorithm Library and Editor) by the authors, and deduce an algorithm for finding a Kuratowski subdivision in a DFS cotree-critical graph.

Regular orientations, that is orientations such that almost all the vertices have the same indegree, relates many combinatorial and topological properties, such as arboricity, page number, and planarity. Those orientations are a basic tool in solving combinatorial problems that preserve topological properties. Planar augmentations are a simple example of such problems.

The traversal of a self crossing closed plane curve, with points of multiplicity at most two, defines a double occurrence sequence.
C.F. Gauss conjectured that such sequences could be characterized by their interlacement properties. This conjecture was proved by P. Rosenstiehl in 1976. We shall give here a simple self-contained proof of his characterization. This new proof relies on the D-switch operation.

We present a simple linear time algorithm finding a Kuratowski subdivision in a DFS cotree critical graphs, based on recent theoretical results. For sake of clarity, we shall outline the proofs of the Theorem we make use of. This algorithm is the last part of the two step linear time Kuratowski finding algorithm implemented in PIGALE (``Public Implementation of a Graph Algorithm Library and Editor'', freely available at http://pigale.sourceforge.org).

We prove that a contact system of Jordan arcs is stretchable if and only if it is extendable into a weak arrangement of pseudo-lines.

Intermediate between texts and pictures, diagrams are a natural presentation scheme for computer-human interface. For instance, hierarchical diagrams are an usual tool for engineering and documentation of complex systems. Although the handmade documentation is restricted to particular views of the system, an automatic diagram drawer allows the production of query-driven functional subsystems.

Pigale intègre une librairie d'algorithmes de traitements de graphe écrite en langage C++ et un éditeur de graphe basé sur les librairies Qt et OpenGL. Ce programme est particulièrement destiné à la recherche théorique sur les graphes topologiques. Pigale est disponible sous licence GPL et peut être téléchargé par FTP ou CVS depuis l'adresse: http://sourceforge.net/projects/pigale/