Unimaximal Sequences of Pairs in Rectangle Visibility Drawing

Stola, Jan (2009) Unimaximal Sequences of Pairs in Rectangle Visibility Drawing. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 61-66 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_7).

Full text not available from this repository.


We study the existence of unimaximal subsequences in sequences of pairs of integers, e.g., the subsequences that have exactly one local maximum in each component of the subsequence. We show that 1 every sequence of 12 n2 (n2 − 1) + 1 pairs has a unimaximal subsequence of length n. We prove that this bound is tight. We apply this result to the problem of the largest complete graph with a 3D rectangle visibility representation and improve the upper bound from 55 to 50.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_7
Classifications:G Algorithms and Complexity > G.280 Canonical Ordering
P Styles > P.720 Straight-line
Z Theory > Z.999 Others
P Styles > P.060 3D
ID Code:896

Repository Staff Only: item control page


Fekete, S.P., Houle, M.E., Whitesides, S.: New results on a visibility representation of graphs in 3D. In: Brandenburg, F.J. (ed.) GD 95. LNCS, vol. 1027, pp. 234–241. Springer, Heidelberg (1996)

Bose, P., Everett, H., Fekete, S.P., Lubiw, A., Meijer, H., Romanik., K., Shermer, T., Whitesides, S.: On a visibility representation for graphs in three dimensions. In: Di Battista, G., Eades, P., de Fraysseix, H., Rosenstiehl, P., Tamassia, R. (eds.) GD 93, pp. 38–39 (1993)

Chung, F.R.K.: On unimodal subsequences. J. Combinatorial Theory 29(A), 267– 279 (1980)

Erdos, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Math. 2, o 463–470 (1935)

Stola, J.: Colorability in orthogonal graph drawing. In: Hong, S.H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 327–338. Springer, Heidelberg (2007)

Alt, H., Godau, M., Whitesides, S.: Universal 3-dimensional visibility representations for graphs. In: Brandenburg, F.J. (ed.) GD 95. LNCS, vol. 1027, pp. 8–19. Springer, Heidelberg (1996)

Romanik, K.: Directed VR-Representable Graphs have Unbounded Dimension. In: Tamassia, R., Tollis, I.G. (eds.) GD 94. LNCS, vol. 894, pp. 177–181. Springer, Heidelberg (1995)

Fekete, S.P., Meijer, H.: Rectangle and box visibility graphs in 3D. Int. J. Comput. Geom. Appl. 97, 1–28 (1997)