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.
Repository Staff Only: item control page