Abstract Given a plane graph $G=(V,E)$ , a Petrie tour of G is a tour P of G that alternately turns left and right at each step. A Petrie tour partition of G is a collection ${\mathscr P}=\{P_1,\ldots,P_q\}$ of Petrie tours so that each edge of G is in exactly one tour $P_i \in {\mathscr P}$ . A Petrie tour P is called a Petrie cycle if all its vertices are distinct. A Petrie cycle partition of G is a collection ${\mathscr C}=\{C_1,\ldots,C_p\}$ of Petrie cycles so that each vertex of G is in exactly one cycle $C_i \in {\mathscr C}$ . In this paper, we study the properties of 3-regular plane graphs that have Petrie cycle partitions and 4-regular plane multi-graphs that have Petrie tour partitions. Given a 4-regular plane multi-graph $G=(V,E)$ , a 3-regularization of G is a 3-regular plane graph $G_3$ obtained from G by splitting every vertex $v\in V$ into two degree-3 vertices. G is called Petrie partitionable if it has a 3-regularization that has a Petrie cycle partition. The general version of this problem is motivated by a data compression method, tristrip, used in computer graphics. In this paper, we present a simple characterization of Petrie partitionable graphs and show that the problem of determining if G is Petrie partitionable is NP-complete.

In this paper, we propose a data structure, a quadruple neighbor list (QN-list, for short), to support real time queries of all longest increasing subsequence (LIS) and LIS with constraints over sequential data streams. The QN-List built by our algorithm requires O(w) space, where w is the time window size. The running time for building the initial QN-List takes O(w logw) time. Applying the QN-List, insertion of the new item takes O(logw) time and deletion of the first item takes O(w) time. To the best of our knowledge, this is the first work to support both LIS enumeration and LIS with constraints computation by using a single uniform data structure for real time sequential data streams. Our method outperforms the state-of-the-art methods in both time and space cost, not only theoretically, but also empirically.

In this paper, we propose a data structure, a quadruple neighbor list (QN-list, for short), to support real time queries of all longest increasing subsequence (LIS) and LIS with constraints over sequential data streams. The QN-List built by our algorithm requires O ( w ) space, where w is the time window size. The running time for building the initial QN-List takes O ( w log w ) time. Applying the QN-List, insertion of the new item takes O (log w ) time and deletion of the first item takes O ( w ) time. To the best of our knowledge, this is the first work to support both LIS enumeration and LIS with constraints computation by using a single uniform data structure for real time sequential data streams. Our method outperforms the state-of-the-art methods in both time and space cost, not only theoretically, but also empirically.

Geometric routing by using virtual locations is an ele gant way for solving network routing problems. In its simplest form, greedy routing, a message is simply for warded to a neighbor that is closer to the destination. It has been an open conjecture whether every 3-connected plane graph has a greedy drawing in R2 (by Papadimitriou and Ratajczak [23]). Leighton and Moitra [20] recently settled this conjecture positively. One main drawback of this approach is that the coordinates of the virtual locations requires Ω(n log n) bits to repre sent (the same space usage as traditional routing table approaches). This makes greedy routing infeasible in applications. A similar result was obtained by Angelini et al. [2]. However, neither of the two papers give the time efficiency analysis of their algorithms. In addition, as pointed out in [16], the drawings in these two papers are not necessarily planar nor convex. In this paper, we show that the classical Schnyder drawing in R2 of plane triangulations is greedy with respect to a simple natural metric function H(u, v) over R2 that is equivalent to Euclidean metric DE(u, v) (in the sense that DE(u,v) < H(u, v) ≤ 2√2 DE(u, v).) The drawing is succinct, using two integer coordinates between 0 and 2n − 5. For 3-connected plane graphs, there is another conjecture by Papadimitriou and Ratajczak (as stated in [16]): Convex Greedy Embedding Conjecture: Every 3-connected planar graph has a convex greedy embedding in the Euclidean plane. In a recent paper [6], Cao et al. provided a plane graph G and showed that any convex greedy embedding of G in Euclidean plane must use Ω(n)-bit coordinates Thus, if we add the succinctness requirement, the Convex Greedy Embedding Conjecture is false In this paper, we show that the classical Schnyder drawing in R2 of 3-connected plane graphs is weakly greedy with respect to the same metric function H(*, *) The drawing is planar, convex, and succinct, using two integer coordinates between 0 and f (where f is the number of internal faces of G).

The visibility representation (VR for short) is a classical representation of plane graphs. The VR has various applications and has been extensively studied in the literature. One of the main focuses of the study is to minimize the size of the VR. It is known that there exists a plane graph G with n vertices, where any VR of G requires a size at least $(\lfloor \frac{2n}{3} \rfloor) \times (\lfloor \frac{4n}{3} \rfloor -3)$. For upper bounds, it is known that every plane graph has a VR with height at most $\lfloor \frac{4n-1}{5} \rfloor$, and a VR with width at most $\lfloor \frac{13n-24}{9} \rfloor$. In this paper, we prove that every plane graph has a VR with height at most $\frac{2n}{3}+2\lceil \sqrt{n/2}\rceil$, and a VR with width at most $\frac{4n}{3}+2\lceil \sqrt{n}\rceil$. These representations are nearly optimal in the sense that they differ from the lower bounds only by a lower order additive term. Both representations can be constructed in linear time. Our presentations use Schnyder's realizer to construct the $st$-orientations of plane graphs with special properties. As the $st$-orientation is a very useful concept in other applications, this result may be of independent interest.

Recently, Hoffmann and Kriegel proved an important combinatorial theorem [SIAM J. Discrete Math., 9 (1996), pp. 210--224]: Every 2-connected bipartite plane multigraph G without 2-cycle faces has a triangulation in which all vertices have even degree (this is called an even triangulation). Combined with the classical Whitney's theorem, this result implies that every such graph has a 3-colorable plane triangulation. Using this theorem, Hoffmann and Kriegel significantly improved the upper bounds of several art gallery and prison guard problems. A complicated O(n 2 ) time algorithm was obtained in [SIAM J. Discrete Math., 9 (1996), pp. 210--224] for constructing an even triangulation of G. Hoffmann and Kriegel conjectured that there is an O(n 3/2 ) time algorithm for solving this problem. In this paper, we develop a simple proof of the above theorem. Our proof reveals and relies on a natural correspondence between even triangulations of G and certain orientations of G. Based on this new proof, we obtain a very simple O(n) time algorithm for finding an even triangulation of G. We also extend our proof to show the existence of even triangulations for similar graphs on high genus surface.