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.

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.

Given a planar graph $\Ggg$ and a sequence ${\CC}_1,\ldots,{\CC}_q$, where each ${\CC}_i$ is a family of vertex subsets of $\Ggg$, we wish to find a plane embedding of $\Ggg$, if any exists, such that, for each $i\in\{1,\ldots,q\}$, there is a face F i in the embedding whose boundary contains at least one vertex from each set in CC i . This problem has applications in the recovery of topological information from geographical data and the design of constrained layouts in VLSI. Let $\inputsize$ be the input size,i.e., the total number of vertices and edges in $\Ggg$ and the families CC i , counting multiplicity. We show that this problem is NP-complete in general. We also show that it is solvable in $O(\inputsize\log \inputsize)$ time for the special case in which, for each input family CC i , each set in CC i induces a connected subgraph of the input graph $\Ggg$. Note that the classical problem of simply finding a planar embedding is a further special case of this case with q=0. Therefore, the processing of the additional constraints CC 1 , . . .,CC q incurs only a logarithmic factor of overhead.

This paper answers an open question in the design of complimentary metal-oxide semiconductor VLSI circuits. The question asks whether a polynomial-time algorithm can decide if a given planar graph has a plane embedding ${\cal E}$ such that ${\cal E}$ has an Euler trail P = e 1 e 2 ... e m and its dual graph has an Euler trail $P^*=e^*_1 e^*_2 \ldots e^*_m$, where $e^*_i$ is the dual edge of e i for i=1,2,...,m. This paper answers this question in the affirmative by presenting a linear-time algorithm.

We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property $\pi$ is called a {\em $\pi$-graph}. If $\pi$ satisfies certain properties, then an n-node m-edge $\pi$-graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most $\beta(n)+o(\beta(n))$ bits for any continuous superadditive function $\beta(n)$ so that there are at most $2^{\beta(n)+o(\beta(n))}$ distinct n-node $\pi$-graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such $\pi$ include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) G is directed or undirected; (3) G is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from $\{1,\ldots, \ell_1\}$ for $\ell_1\leq n$; (5) the edges of G are labeled with labels from $\{1,\ldots, \ell_2\}$ for $\ell_2\leq m$; and (6) each node (respectively, edge) of G has at most $\ell_3=O(1)$ self-loops (respectively, $\ell_4=O(1)$ multiple edges). Moreover, $\ell_3$ and $\ell_4$ are not required to be O(1) for the cases of $\pi$ being a plane triangulation. These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes.

The paper answers an open question in the design of complimentary metal-oxide semiconductor (CMOS) VLSI circuits. It asks whether a polynomial-time algorithm can decide if a given planar graph has a plane embedding /spl epsiv/ such that /spl epsiv/ has a Euler trail P=e/sub 1/e/sub 2/...e/sub m/ and its dual graph has a Euler trail P*=e/sub 1/*e/sub 2/*...e/sub m/* where e/sub i/* is the dual edge of e/sub i/ for i=1, 2, ..., m. The paper answers this question in the affirmative by presenting a linear-time algorithm.

The traveling salesman problem on an n-point convex polygon and the minimum latency tour problem for n points on a straight line are two basic problems in graph theory and have been studied in the past. Previously, it was known that both problems can be solved in O(n 2 ) time. However, whether they can be solved in o(n 2 ) time was left open by Marcotte and Suri [SIAM J. Comput., 20 (1991), pp. 405--422] and Afrati et al. [Informatique Theorique Appl., 20 (1986), pp. 79--87], respectively. In this paper we show that both problems can be solved in O(n log n) time by reducing them to the following problem: Given an edge-weighted complete bipartite digraph G=(X, Y, E) with X={x 0 , . . ., x n } and Y={y 0 , . . ., y m }, we wish to find the shortest path from x 0 to x n in G. This new problem requires $\Omega(nm)$ time to solve in general, but we show that it can be solved in O(n + m log n) time if the weight matrices A and B of G are both concave, where for $0\leq i\leq n$ and $0\leq j\leq m$, A[i,j] and B[j,i] are the weights of the edges (x i , y j ) and (y j , x i ) in G, respectively. As demonstrated in this paper, the new problem is a powerful tool and we believe that it can be used to solve more problems.

Let G be an embedded planar undirected graph that has n vertices, m edges, and f faces but has no self-loop or multiple edge. If G is triangulated, we can encode it using 4/3m-1 bits, improving on the best previous bound of about 1.53m bits. In case exponential time is acceptable, roughly 1.08m bits have been known to suffice. If G is triconnected, we use at most $(2.5+2\log{3})\min\{n,f\}-7$ bits, which is at most 2.835m bits and smaller than the best previous bound of 3m bits. Both of our schemes take O(n) time for encoding and decoding.

Article Free Access Share on On floorplans of planar graphs Author: Xin He Department of Computer Science, State University of New York at Buffalo, Buffalo, NY Department of Computer Science, State University of New York at Buffalo, Buffalo, NYView Profile Authors Info & Claims STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computingMay 1997 Pages 426–435https://doi.org/10.1145/258533.258633Online:04 May 1997Publication History 4citation1,219DownloadsMetricsTotal Citations4Total Downloads1,219Last 12 Months7Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A straight-line grid embedding of a planar graph is a drawing of the graph on a plane where the vertices are located at grid points and the edges are represented by nonintersecting segments of straight, lines joining their incident vertices. Given an n-vertex embedded planar graph with $n \geq 3$, a straight-line embedding on a grid of size $( n - 2 ) \times ( n - 2 )$ can be computed deterministically in $O( \log n\log \log n )$ time with $n/\log n\log \log n$ processors. If randomization is used, the complexity is improved to $O( \log n )$ expected time with the same optimal linear work. These algorithms run on a parallel random access machine that allows concurrent reads and concurrent writes of the shared memory and permits an arbitrary processor to succeed in case of a write conflict.

A straight-line grid embedding of a planar graph is a drawing of the graph on a plane where the vertices are located at grid points and the edges are represented by nonintersecting segments of straight lines joining their incident vertices.Given an n-vertex planar graph with n ~3, a straight-line embedding on a grid of size (n-2)X(n-2) can be computed deterministically in O(log n log log n) time with O(n log log n) work on a parallel random access machine.If randomization is used, the complexity is improved to O(log n) expected time with the same work bound.The parallel random access machine used by these algorithms allows concurrent reads and concurrent writes of the shared memory; in case of a write conflict, an arbitrary processor succeeds.sonably small grids are very useful in visualizing planar graphs on graphic screens and have wide applications in CAD/CAM and Computer Graphics [8], [27].Wagner [28], Fziry [9], and Stein [24] showed that every planar graph has a straight-line embedding.Since

This paper presents a parallel algorithm for constructing depth first spanning trees in planar graphs. The algorithm takes $O(\log ^2 n)$ time with $O(n)$ processors on a concurrent read concurrent write parallel random access machine (PRAM). The best previously known algorithm for the problem takes $O(\log ^3 n)$ time with $O(n^4 )$ processors on a PRAM. Our algorithm is within an $O(\log ^2 n)$ factor of optimality.