Series-Parallel Planar Ordered Sets Have Pagenumber Two (Extended Abstract)

Alzohairi, Mohammad and Rival, Ivan (1997) Series-Parallel Planar Ordered Sets Have Pagenumber Two (Extended Abstract). In: Symposium on Graph Drawing, GD '96, September 18-20, 1996, Berkeley, California, USA , pp. 11-24 (Official URL: http://dx.doi.org/10.1007/3-540-62495-3_34).

Full text not available from this repository.

Abstract

The page number of a series-parallel planar P is at most two. We present an O(n^3) algorithm to construct a two-page embedding in the case that it is a lattice. One consequence of independent interest, is a characterization of series-parallel planar ordered sets.

Item Type:Conference Paper
Additional Information:10.1007/3-540-62495-3_34
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
ID Code:93

Repository Staff Only: item control page

References

F. Bernhart and P. C. Kainen (1979) The book thickness of a graph, Journal of Combinatorial Theory, Series B 27, 320-331.

G. Birkhoff (1967) Lattice Theory, American Mathematical Society, Providence, Rhode Island.

L. T. Q. Hung (1993) A Planar Poset which Requires four Pages, Ars Combin 35, 291-302

H. de Fraysseix, P. O. de Mendez and J. Pach (1995) A Left Search Algorithm for Planar Graphs, Discrete Comput. Geom. 13, 459-468.

D. Kelly and I. Rival (1975) Planar lattices, Canad. Journal of Mathematics 27, 636-665.

H. M. MacNeille (1937) Partially ordered sets, Trans. Amer. Math. Soc. 42, 416-460.

R. Nowakowski and A. Parker (1989), Ordered sets, pagenumbers and planarity, Order 6, 209-218.

S. V. Pemmaraju (1992) Exploring the Powers of Stacks and Queues via Graph Layouts, Ph.D. thesis, Virginia Polytechnic Institute and State University at Blacksburg, Virginia.

M. M. Syslo (1990) Bounds to the Page Number of Partially Ordered Sets, Graph-theoretic concepts in computer science (Kerkrade, 1989),181-195, Lecture Notes in Comput. Sci. 411. Springer, Berlin.

J. Valdes, R. E. Tarjan and E. L. Lawler (1982) The recognition of series-parallel digraphs, SIAM J. Computing 11, 298-314.

M. Yannakakis (1989) Embedding planar graphs in four pages, J. Comput. System Sci. 38, 36-67.