On topological aspects of orientations

De Fraysseix, Hubert and Ossona de Mendez, Patrice (2001) On topological aspects of orientations. [Journal (Paginated)]

Full text not available from this repository.

Abstract

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 linear time algorithms.

Item Type:Journal (Paginated)
Additional Information:10.1016/S0012-365X(00)00201-6
Classifications:Z Theory > Z.750 Topology
G Algorithms and Complexity > G.280 Canonical Ordering
Z Theory > Z.999 Others
G Algorithms and Complexity > G.999 Others
ID Code:735

Repository Staff Only: item control page

References

H. de Fraysseix, T. Matsumoto, P. Ossona de Mendez, P. Rosenstiehl, Regular orientations and graph drawing, Third Slovenian International Conference in Graph Theory, 1995.

H. de Fraysseix, P. Ossona de Mendez, Connectivity of planar graphs, Dagsthul Seminar Proceedings, JGAA, 5(5):93-105, 2001.

H. de Fraysseix, P. Ossona de Mendez, On regular orientations, Prague Midsummer Combinatorial Workshop, 1994, pp. 9-13.

H. de Fraysseix, P. Ossona de Mendez, Regular orientations, arboricity and augmentation, DIMACS International Workshop, Graph Drawing '94, Lecture Notes in Computer Science, Vol. 894, Springer, Berlin, 1995, pp. 111-118.

H. de Fraysseix, P. Ossona de Mendez, Planarity and edge poset dimension, European J. Combin. 17 (1997) 731-740.

H. de Fraysseix, P. Ossona de Mendez, A left-first search algorithm for planar graphs, Discrete Comput. Geom. 13 (1995) 459-468.

H. de Fraysseix, P. Ossona de Mendez, P. Rosenstiehl, On triangle contact graphs, Combinatorics, Probab. Comput. 3 (1994) 233-246.

H. de Fraysseix, P. Ossona de Mendez, P. Rosenstiehl, Bipolar orientations revisited, Discrete Appl. Math. 56 (1995) 157-179.

H. de Fraysseix, J. Pach, R. Pollack, Small sets supporting Fary embeddings of planar graphs, Twentieth Annual ACM Symposium on Theory of Computing, 1988, pp. 426-433.

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

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

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

G. Kant, Algorithms for drawing planar graphs, Ph.D. Thesis, Utrecht University, Utrecht, 1993.

M. Las Vergnas, Acyclic and totally cyclic orientations of combinatorial geometries, Discrete Math. 20 (1977) 51-61.

A. Mach, Orientations of planar graphs with condition on the angles, Internal Report L.I.T.P., 1992.

T. Matsumoto, Orientations contraintes, Ph.D. Thesis, Ecole des Hautes Etudes en Sciences Sociales, Paris, 1997.

C.St.J.A. Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. London Math. Soc. 36 (1961) 445-450.

C.St.J.A. Nash-Williams, Decomposition of finite graphs into forests, J. London Math. Soc. 39 (1964) 12.

P. Ossona de Mendez, Geometric realization of simplicial complexes, in: I. Kratochvil, ed., Graph Drawing, Lecture Notes in Computer Science, Vol. 1731, Springer, Berlin, 1999, pp. 323-332.

P. Ossona de Mendez, Orientations bipolaires, Ph.D. Thesis, Ecole des Hautes Etudes en Sciences Sociales, Paris, 1994.

V. Petrovic, Decomposition of some planar graphs into trees, Proceedings of International Conference on Combinatorics, J. Bolyai Mathematical Society, 1993, p. 48.

V. Petrovic, G. Ringel, C. Thomassen, Decomposition of maximal graphs into trees, preprint, 1993.

G. Ringle, Two trees in maximal planar bipartite graphs, J. Graph Theory 17 (6) (1993) 755-758.

P. Rosenstiehl, R.E. Tarjan, Rectilinear planar layout and bipolar orientation of planar graphs, Discrete Comput. Geom. 1 (1986) 343-353.

W. Schnyder, Planar graphs and poset dimension, Order 5 (1989) 323-343.

W. Schnyder, Embedding planar graphs in the grid, First ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 138-147.

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

D. Woods, Drawing planar graphs, Ph.D. Thesis, Stanford University, 1982, Technical Report STAN-CS-82-943.