×

Orthogonal surfaces and their CP-orders. (English) Zbl 1149.05036

Summary: Orthogonal surfaces are nice mathematical objects which have interesting connections to various fields, e.g., integer programming, monomial ideals and order dimension. While orthogonal surfaces in one or two dimensions are rather trivial already the three dimensional case has a rich structure with connections to Schnyder woods, planar graphs and three-polytopes. Our objective is to detect more of the structure of orthogonal surfaces in four and higher dimensions. In particular we are driven by the question which non-generic orthogonal surfaces have a polytopal structure. We review the state of knowledge of the three-dimensional situation. On that basis we introduce terminology for higher dimensional orthogonal surfaces and continue with the study of characteristic points and the cp-orders of orthogonal surfaces, i.e., the dominance orders on the characteristic points. In the generic case these orders are (almost) face lattices of polytopes. Examples show that in general cp-orders can lack key properties of face lattices. We investigate extra requirements which may help to have cp-orders which are face lattices. Finally, we turn the focus and ask for the realizability of polytopes on orthogonal surfaces. There are criteria which prevent large classes of simplicial polytopes from being realizable. On the other hand we identify some families of polytopes which can be realized on orthogonal surfaces.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
06A07 Combinatorics of partially ordered sets
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adin, R.M., Roichman, Y.: On degrees in the Hasse diagram of the strong Bruhat order. Sém. Lothar. Combin. 53 (B53g), 12p (2006) · Zbl 1186.05001
[2] Agnarsson, G., Felsner, S., Trotter, W.T.: The maximum number of edges in a graph of bounded dimension, with applications to ring theory. Discrete Math. 201, 5–19 (1999) · Zbl 0936.05061 · doi:10.1016/S0012-365X(98)00309-4
[3] Alon, N., Füredi, Z., Katchalski, M.: Separating pairs of points. Europ. J. Comb. 6, 205–210 (1985) · Zbl 0592.05002
[4] Babai, L., Duffus, D.: Dimension and automorphism groups of lattices. Algebra Univers. 12, 279–289 (1981) · Zbl 0495.06002 · doi:10.1007/BF02483890
[5] Bárány, I., Rote, G.: Strictly convex drawings of planar graphs. Doc. Math. 11, 369–391 (2006) · Zbl 1108.05065
[6] Bayer, D., Peeva, I., Sturmfels, B.: Monomial resolutions. Math. Res. Lett. 5, 31–46 (1998) · Zbl 0909.13010
[7] Bonichon, N., Felsner, S., Mosbah, M.: Convex drawings of 3-connected planar graphs. Algorithmica 47, 399–420 (2007) · Zbl 1118.68100 · doi:10.1007/s00453-006-0177-6
[8] Bonichon, N., Le Saëc, B., Mosbah, M.: Optimal area algorithm for planar polyline drawings. In: Proceedings WG’02, Lecture Notes Comput. Sci., vol. 2573, pp. 35–46. Springer-Verlag (2002) · Zbl 1022.68593
[9] Brightwell, G., Trotter, W.T.: The order dimension of convex polytopes. SIAM J. Discrete Math. 6, 230–245 (1993) · Zbl 0779.06003 · doi:10.1137/0406018
[10] de Fraysseix, H., de Mendez, P.O.: On topological aspects of orientation. Discrete Math. 229, 57–72 (2001) · Zbl 0980.05023 · doi:10.1016/S0012-365X(00)00201-6
[11] Di Battista, G., Tamassia, R., Vismara, L.: Output-sensitive reporting of disjoint paths. Algorithmica 23, 302–340 (1999) · Zbl 0921.68063 · doi:10.1007/PL00009264
[12] Felsner, S.: Convex drawings of planar graphs and the order dimension of 3-polytopes. Order 18, 19–37 (2001) · Zbl 0984.05029 · doi:10.1023/A:1010604726900
[13] Felsner, S.: Geodesic embeddings of planar graphs. Order 20, 135–150 (2003) · Zbl 1033.05028 · doi:10.1023/B:ORDE.0000009251.68514.8b
[14] Felsner, S.: Geometric Graphs and Arrangements. Vieweg Verlag (2004) · Zbl 1051.05036
[15] Felsner, S.: Lattice structures from planar graphs. Electron. J. Combin. 11, 24p (2004) · Zbl 1056.05039
[16] Felsner, S.: Empty rectangles and graph dimension. (2006) http://arxiv.org/abs/math.CO/0601767
[17] Felsner, S., Trotter, W.T.: Posets and planar graphs. J. Graph Theory 49, 262–272 (2005) · Zbl 1068.05033 · doi:10.1002/jgt.20081
[18] Felsner, S., Zickfeld, F.: Schnyder woods and orthogonal surfaces. In Proceedings Graph Drawing, pp. 417–429, Karlsruhe, Germany (2007) · Zbl 1185.68474
[19] Fusy, E., Poulalhon, D., Schaeffer, G.: Dissection and trees, with applications to optimal mesh encoding and random sampling. In: Proc. 16. ACM-SIAM Sympos. Discrete Algorithms, ACACM Transactions on Algorithms, pp. 690–699 (2005) · Zbl 1297.05053
[20] Grünbaum, B.: Convex polytopes. Graduate Texts in Mathematics, vol. 221. Springer-Verlag (2003) · Zbl 1033.52001
[21] Hoşten, S., Morris, W.D.: The order dimension of the complete graph. Discrete Math. 201, 133–139 (1999) · Zbl 0932.06003 · doi:10.1016/S0012-365X(98)00315-X
[22] Kappes, S.: Orthogonal surfaces: A combinatorial approach. PhD thesis. (2006). http://www.math.tu-berlin.de/diskremath/sarahs_diss.pdf · Zbl 1225.52002
[23] Lin, C., Lu, H., Sun, I.-F.: Improved compact visibility representation of planar graphs via Schnyder’s realizer. SIAM J. Discrete Math. 18, 19–29 (2004) · Zbl 1068.05046 · doi:10.1137/S0895480103420744
[24] Miller, E.: Planar graphs as minimal resolutions of trivariate monomial ideals. Documenta Math. 7, 43–90 (2002) · Zbl 0989.05026
[25] Miller, E., Sturmfels, B.: Combinatorial Commutative Algebra. Graduate Texts in Mathematics, Springer-Verlag (2004)
[26] Poulalhon, D., Schaeffer, G.: Optimal coding and sampling of triangulations. Algorithmica 46, 505–527 (2006) · Zbl 1106.68114 · doi:10.1007/s00453-006-0114-8
[27] Scarf, H.: The Computation of Economic Equilibria. Cowles Foundation Monograph, vol. 24. Yale University Press (1973) · Zbl 0311.90009
[28] Schnyder, W.: Planar graphs and poset dimension. Order 5, 323–343 (1989) · Zbl 0675.06001 · doi:10.1007/BF00353652
[29] Schnyder, W.: Embedding planar graphs on the grid. In: Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pp. 138–148 (1990) · Zbl 0786.05029
[30] Spencer, J.: Minimal scrambling sets of simple orders. Acta Math. Acad. Sci. Hungar. 22, 349–353 (1972) · Zbl 0242.05001 · doi:10.1007/BF01896428
[31] Trotter, W.T.: Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins Series in the Mathematical Sciences. The Johns Hopkins University Press (1992) · Zbl 0764.05001
[32] Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152 Springer-Verlag (1994) · Zbl 0890.60029
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.