P.I.G.A.L.E.Public Implementation of a Graph AlgorithmLibrary and EditorH. de Fraysseix P. Ossona de Mendez |

[1] | W.T. Tutte. Convex representations of graphs. In Proc. London Math. Society, volume 10, pages 304-320,
1960. |

[2] | W.T. Tutte. How to draw a graph. In Proc. London Math. Society, volume 13, pages 743-768,
1963. |

[3] | H. de Fraysseix and P. Rosenstiehl. A depth-first search characterization of planarity. Annals of
Discrete Mathematics, 13:75-80, 1982. |

[4] | H. de Fraysseix and P. Rosenstiehl. A discriminatory theorem of Kuratowski subgraphs. In
J.W. Kennedy M. Borowiecki and M.M. Sysl o, editors, Graph Theory, Lagów 1981, volume 1018 of
Lecture Notes in Mathematics, pages 214-222. Springer-Verlag, 1983. Conference dedicated to the memory of
Kazimierz Kuratowski. |

[5] | H. de Fraysseix and P. Rosenstiehl. Système de référence de Trémaux d'une représentation plane d'un
graphe planaire. Annals of Discrete Mathematics, 17:293-302, 1983. |

[6] | H. de Fraysseix and P. Rosenstiehl. A characterization of planar graphs by Trémaux orders.
Combinatorica, 5(2):127-135, 1985. |

[7] | P. Rosenstiehl and R.E. Tarjan. Rectilinear planar layout and bipolar orientation of planar graphs.
Discrete and Computational Geometry, 1:343-353, 1986. |

[8] | H. de Fraysseix, J. Pach, and R. Pollack. Small sets supporting Fary embeddings of planar
graphs. In Twentieth Annual ACM Symposium on Theory of Computing, pages 426-433, 1988. |

[9] | W. Schnyder. Planar graphs and poset dimension. Order, 5:323-343, 1989. |

[10] | W. Schnyder. Embedding planar graphs in the grid. In First ACM-SIAM Symposium on Discrete Algorithms,
pages 138-147, 1990. |

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

[12] | H. de Fraysseix, P. Ossona de Mendez, and J. Pach. Representation of planar graphs by
segments. Intuitive Geometry, 63:109-117, 1991. |

[13] | H. de Fraysseix and P. Kuntz. Pagination of large scale networks. Algorithms review,
2(3):105-112, 1992. |

[14] | H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. On triangle contact graphs.
Combinatorics, Probability and Computing, 3:233-246, 1994.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. |

[15] | H. de Fraysseix and P. Ossona de Mendez. Regular Orientations, Arboricity and Augmentation. In
DIMACS International Workshop, Graph Drawing 94, volume 894 of Lecture notes in Computer Science, pages
111-118, 1995.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. These orientations are a basic tool in solving combinatorial problems that preserve topological properties. Planar augmentations are a simple example of such problems. |

[16] | H. de Fraysseix, P. Ossona de Mendez, and J. Pach. A Left-First Search Algorithm for
Planar Graphs. Discrete Computational Geometry, 13:459-468, 1995.We give an |

[17] | Gilles Schaeffer. Random sampling of large planar maps and convex polyhedra. In Annual ACM Symposium on Theory
of Computing (Atlanta, GA, 1999), pages 760-769 (electronic). ACM, New York, 1999. |

[18] | H. de Fraysseix. An heuristic for graph symmetry detection. In J. Kratochvil, editor, Graph
Drawing, volume 1731 of Lecture Notes in Computer Science, pages 276-285. Springer, 1999. |

[19] | H. de Fraysseix and P. Ossona de Mendez. On topological aspects of orientations. Discrete
Mathematics, 229(1-3):57-72, 2001.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. |

[20] | H. de Fraysseix and P. Ossona de Mendez. Connectivity of planar graphs. Journal of Graph
Algorithms and Applications, 5(5):93-105, 2001.[ .ps.gz | .pdf ] |

[21] | H. de Fraysseix and P. Ossona de Mendez. An algorithm to find a Kuratowski subdivision in DFS
cotree critical graphs. In Edy Try Baskoro, editor, Proceedings of the Twelfth Australasian Workshop on
Combinatorial Algorithms (AWOCA 2000), pages 98-105, Indonesia, 2001. Institut Teknologi Bandung.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). |

[22] | N. Bonichon, B. Le Saëc, and M. Mosbah. Optimal area algorithm for planar polyline drawings. In
28, volume 2573 of
^{th} International Workshop, Graph - Theoretic Concepts in Computer Science (WG)LNCS, pages 35-46. Springer-Verlag, 2002.[ .ps.gz ] |

[23] | H. de Fraysseix and P. Ossona de Mendez. A characterization of DFS cotree critical graphs. In
Graph Drawing, volume 2265 of Lecture notes in Computer Science, pages 84-95, 2002.We give a characterization of DFS-cotree critical graphs which is central to the linear time Kuratowski finding algorithm implemented in PIGALE |

[24] | H. de Fraysseix and P. Ossona de Mendez. On cotree-critical and DFS cotree-critical graphs.
Journal of Graph Algorithms and Applications, 7(4):411-427, 2003.[ .pdf ] 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. |

[25] | N. Bonichon, C. Gavoille, and N. Hanusse. Canonical decomposition of outerplanar maps and
application to enumeration, coding and generation. In 29, volume 2880 of ^{th} International Workshop, Graph - Theoretic
Concepts in Computer Science (WG)Lecture Notes in Computer Science, pages 81-92.
Springer-Verlag, June 2003.[ .ps.gz ] |

[26] | N. Bonichon, S. Felsner, and M. Mosbah. Convex drawings of 3-connected planar graphs - (extended
abstract). In Graph Drawing 2004, 2004. submitted. |

[27] | J.M. Boyer, P.F. Cortese, M. Patrignani, and G. Di Battista. Stop minding your P's and Q's:
implementing fast and simple DFS-based planarity and embedding algorithm. In Graph Drawing, volume 2912 of
Lecture Notes in Computer Science, pages 25-36. Springer, 2004. |

[28] | E. Fusy, D. Poulalhon, and G.Schaeffer. Coding, counting and sampling 3-connected planar graphs. In
16, 2005. to appear.^{th} ACM-SIAM Sympos. Discrete Algorithms |

[29] | M. Matsumoto and T. Nishimura. A 623-Dimensionally Equidistributed Uniform
Pseudo-Random Number Generator. In
ACM Transactions on Modeling and Computer Simulation,Vol. 8, No. 1, January 1998, pp 3--30 . |

Last modified: Wed Feb 22 CET 2012