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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/896

Actions (login required)

View Item View Item