×

Simultaneous dominance representation of multiple posets. (English) Zbl 0873.06003

Summary: We characterize the codominance pairs – pairs of posets that admit simultaneous dominance representations in the \((x,y)\)- and \((-x,y)\)-coordinate systems – and present a linear algorithm to recognize them and construct codominance representations. We define dominance polysemy as a generalization of codominance and describe several related problems and preliminary results.

MSC:

06A07 Combinatorics of partially ordered sets
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brightwell, G. and Winkler, P. (1989) Sphere orders, Order 6, 235-240. · Zbl 0695.06001
[2] Brightwell, G. R. and Scheinerman, E. R. (1993) Representations of planar graphs, SIAM J. Discrete Math. 6(2), 214-229. · Zbl 0782.05026
[3] Dushnik, B. and Miller, E. W. (1941) Partially ordered sets., Amer. J. Math. 63, 600-610. · Zbl 0025.31002
[4] Ehrlich, G., Even, S. and Tarjan, R. E. (976) Intersection graphs of curves in the plane, J. Combin. Theory Ser. B 21, 8-20. · Zbl 0348.05113
[5] El Gindy, H., Liotta, G., Lubiw, A., Meijer, H. and Whitesides, S. (1995), Recognizing rectangle of influence drawable graphs, in Tamassia and Tollis [14], pp. 352-363.
[6] Fishburn, P. C. (1985) Interval Orders and Interval Graphs: A Study of Partially Ordered Sets, John Wiley, New York. · Zbl 0551.06001
[7] Fishburn, P. C. and Trotter, W. T.Jr. (1985) Angle orders, Order 1, 333-343. · Zbl 0558.06003
[8] Gilmore, P. C. and Hoffman, A. J. (1964) A characterization of comparability graphs and of interval graphs, Canad. J. Math. 16, 539-548. · Zbl 0121.26003
[9] Goodman, J. E. and Pollack, R. (1980) On the combinatorial classification of nondegenerate configurations in the plane, J. Combin. Theory Ser. A. 29, 220-235. · Zbl 0448.05016
[10] Goodman, J. E. and Pollack, R. (1984) Semispaces of configurations, cell complexes of arrangements, J. Combin. Theory Ser. A 37, 257-293. · Zbl 0551.05002
[11] Preparata, F. P. and Shamos, M. I. (1985) Computational Geometry: An Introduction, Springer-Verlag, New York. · Zbl 0575.68059
[12] Scheinerman, E. R. (1991) A note on planar graphs and circle orders, SIAM J. Discrete Math. 4(3), 448-451. · Zbl 0735.05033
[13] Spinrad, J. (1994) Recognition of circle graphs, J. Algorithms 16, 264-282. · Zbl 0797.68130
[14] Tamassia, R. and Tollis, I. G. (eds.) (1995) Graph Drawing: Proceedings of GD ’94, Lecture Notes in Computer Science, no. 894, Springer-Verlag, Berlin. · Zbl 0806.68007
[15] Tanenbaum, P. J. (1995) On geometric representations of partially ordered sets, Ph.D. Thesis, The Johns Hopkins University.
[16] Tanenbaum, P. J. (1996) Simultaneous representation of interval and interval-containment orders, Order 13, 339-350 (this issue). · Zbl 0874.06003
[17] Tanenbaum, P. J., Goodrich, M. T. and Scheinerman, E. R. (1995) Characterization and recognition of point-halfspace and related orders, in Tamassia and Tollis [14], pp. 234-245.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.